Test Score Algorithms for Budgeted Stochastic Utility Maximization

References

• Aboolian R, Berman O, Krass D (2007) Competitive facility location model with concave demand. Eur. J. Oper. Res. 181(2):598–619.Google Scholar
• Ahmed S, Atamtürk A (2011) Maximizing a class of submodular utility functions. Math. Programming 128:149–169.Google Scholar
• Asadpour A, Nazerzadeh H (2016) Maximizing stochastic monotone submodular functions. Management Sci. 62(8):2374–2391.Link, Google Scholar
• Atamtürk A, Gómez A (2017) Maximizing a class of utility functions over the vertices of a polytope. Oper. Res. 65(2):433–445.Link, Google Scholar
• Babaioff M, Immorlica N, Kempe D, Kleinberg R (2007) A knapsack secretary problem with applications. Internat. Workshop Approximation Algorithms Combin. Optim. Internat. Workshop Randomization Approximation Techniques Comput. Sci., 16–28.Google Scholar
• Badanidiyuru A, Vondrák J (2014) Fast algorithms for maximizing submodular functions. ACM-SIAM Sympos. Discrete Algorithms, 1497–1514.Google Scholar
• Badanidiyuru A, Mirzasoleiman B, Karbasi A, Krause A (2014) Streaming submodular maximization: Massive data summarization on the fly. ACM SIGKDD Internat. Conf. Knowledge Discovery Data Mining, 671–680.Google Scholar
• Bian AA, Mirzasoleiman B, Buhmann J, Krause A (2017) Guaranteed non-convex optimization: Submodular maximization over continuous domains. Singh A, Zhu J, eds. Proc. 20th Internat. Conf. Artificial Intelligence Statist., vol. 54, 111–120.Google Scholar
• Buchbinder N, Naor J (2005) Online primal-dual algorithms for covering and packing. Eur. Sympos. Algorithms, 689–701.Google Scholar
• Buchbinder N, Naor J (2006) Improved bounds for online routing and packing via a primal-dual approach. IEEE Sympos. Foundations Comput. Sci., 293–304.Google Scholar
• Chakrabarti A, Kale S (2015) Submodular maximization meets streaming: matchings, matroids, and more. Math. Programming 154:225–247.Google Scholar
• Chekuri C, Gupta S, Quanrud K (2015) Streaming algorithms for submodular function maximization. Internat. Colloquium Automata, Languages, Programming, 318–330.Google Scholar
• Conforti M, Cornuéjols G (1984) Submodular set functions, matroids and the greedy algorithm: Tight worst-case bounds and some generalizations of the Rado-Edmonds theorem. Discrete Appl. Math. 7(3):251–274.Google Scholar
• Désir A, Goyal V, Segev D, Ye C (2020) Constrained assortment optimization under the Markov chain–based choice model. Management Sci. 66(2):698–721.Link, Google Scholar
• Devanur NR, Jain K, Sivan B, Wilkens CA (2019) Near optimal online algorithms and fast approximation algorithms for resource allocation problems. J. ACM 66(1):1–41.Google Scholar
• El-Arini K, Guestrin C (2011) Beyond keyword search: Discovering relevant scientific literature. ACM SIGKDD Internat. Conf. Knowledge Discovery Data Mining, 439–447.Google Scholar
• Ene A, Nguyen HL (2019) A nearly-linear time algorithm for submodular maximization with a knapsack constraint. Internat. Colloquium Automata, Languages, Programming, 53:1–53:12.Google Scholar
• Feldman M, Karbasi A (2020) Continuous submodular maximization: Beyond DR-submodularity. Larochelle H, Ranzato M, Hadsell R, Balcan MF, Lin H, eds. Advances in Neural Information Processing Systems, vol. 33 (Curran Associates, Inc.), 1404–1416.Google Scholar
• Feldman M, Karbasi K, Kazemi E (2018) Do less, get more: Streaming submodular maximization with subsampling. Advances in Neural Information Processing Systems, 730–740.Google Scholar
• Fu R, Subramanian A, Venkateswaran A (2016) Project characteristics, incentives, and team production. Management Sci. 62(3):785–801.Link, Google Scholar
• Golovin D, Krause A (2011) Adaptive submodularity: Theory and applications in active learning and stochastic optimization. J. Artificial Intelligence Res. 42(1):427–486.Google Scholar
• Gomes R, Krause A (2010) Budgeted nonparametric learning from data streams. Internat. Conf. Internat. Conf. Machine Learn., 391–398.Google Scholar
• Guestrin C, Krause A, Singh AP (2005) Near-optimal sensor placements in Gaussian processes. Internat. Conf. Machine Learn., 265–272.Google Scholar
• Haba R, Kazemi E, Feldman M, Karbasi A (2020) Streaming submodular maximization under a k-set system constraint. Internat. Conf. Machine Learn., 3939–3949.Google Scholar
• Han S, Gómez A, Prokopyev OA (2022) Fractional 0-1 programming and submodularity. J. Global Optimization. Forthcoming.Google Scholar
• Hassani H, Soltanolkotabi M, Karbasi A (2018) Conditional gradient method for stochastic submodular maximization: Closing the gap. Internat. Conf. Artificial Intelligence Statist., 1886–1895.Google Scholar
• Hassidim A, Singer Y (2017) Submodular optimization under noise. Conf Learn Theory, 1069–1122.Google Scholar
• Henig MI (1990) Risk criteria in a stochastic knapsack problem. Oper. Res. 38(5):820–825.Link, Google Scholar
• Herbrich R, Minka T, Graepel T (2007) TrueskillTM: A Bayesian skill rating system. Advances in Neural Information Processing Systems, 569–576.Google Scholar
• Horel T, Singer Y (2016) Maximization of approximately submodular functions. Advances in Neural Information Processing Systems, 3053–3061.Google Scholar
• Huang C-C, Kakimura N (2019) Improved streaming algorithms for maximizing monotone submodular functions under a knapsack constraint. Algorithms and Data Structures (WADS), 438–451.Google Scholar
• Huang C-C, Kakimura N, Yoshida Y (2017) Streaming algorithms for maximizing monotone submodular functions under a knapsack constraint. Approximation, Randomization, and Combinatorial Optimization Algorithms and Techniques (APPROX/RANDOM), 11:1–11:14.Google Scholar
• Immorlica N, Lucier B, Mao J, Syrgkanis V, Tzamos C (2018) Combinatorial assortment optimization. Internat. Conf. Web Internet Econom., 218–231.Google Scholar
• Karimi MR, Lucic M, Hassani H, Krause A (2017) Stochastic submodular maximization: The case of coverage functions. Advances in Neural Information Processing Systems, 6856–6866.Google Scholar
• Kazemi E, Mitrovic M, Zadimoghaddam M, Lattanzi S, Karbasi A (2019) Submodular streaming in all its glory: Tight approximation, minimum memory and low adaptive complexity. Internat. Conf. Machine Learn., 3311–3320.Google Scholar
• Kempe D, Kleinberg J, Tardos É (2003) Maximizing the spread of influence through a social network. ACM SIGKDD Internat. Conf. Knowledge Discovery Data Mining, 137–146.Google Scholar
• Kirchhoff K, Bilmes J (2014) Submodularity for data selection in statistical machine translation. Conf. Empirical Methods Natl. Language Processing, 131–141.Google Scholar
• Klastorin TD (1990) On a discrete nonlinear and nonseparable knapsack problem. Oper. Res. Lett. 9(4):233–237.Google Scholar
• Kleinberg J, Raghu M (2015) Team performance with test scores. ACM Conf. Econom. Comput., 511–528.Google Scholar
• Kleinberg J, Raghu M (2018) Team performance with test scores. ACM Trans. Econ. Comput. 6(3–4):1–26.Google Scholar
• Krause A, Guestrin C (2005) Near-optimal nonmyopic value of information in graphical models. Conf. Uncertainty Artificial Intelligence, 324–331.Google Scholar
• Leskovec J, Krause A, Guestrin C, Faloutsos C, VanBriesen J, Glance N (2007) Cost-effective outbreak detection in networks. ACM SIGKDD Internat. Conf. Knowledge Discovery Data Mining, 420–429.Google Scholar
• Li H (2011) Learning to Rank for Information Retrieval and Natural Language Processing (Morgan & Claypool, San Rafael, CA).Google Scholar
• Lin H, Bilmes J (2010) Multi-document summarization via budgeted maximization of submodular functions. Annual Meeting Assoc. Comput. Linguistics Human Language Tech., 912–920.Google Scholar
• Lin H, Bilmes J (2011) A class of submodular functions for document summarization. Annual Meeting Assoc. Comput. Linguistics Human Language Tech., 510–520.Google Scholar
• Mehta A, Nadav U, Psomas A, Rubinstein A (2020) Hitting the high notes: Subset selection for maximizing expected order statistics. Advances in Neural Information Processing Systems, vol. 33 (Curran Associates, Inc.), 15800–15810.Google Scholar
• Mirzasoleiman B, Jegelka S, Krause A (2018) Streaming non-monotone submodular maximization: Personalized video summarization on the fly. AAAI Conf. Artificial Intelligence, 1379–1386.Google Scholar
• Mirzasoleiman B, Karbasi A, Sarkar R, Krause A (2016) Distributed submodular maximization. J. Machine Learn. Res. 17(1):1–44.Google Scholar
• Mokhtari A, Hassani H, Karbasi A. (2017) Gradient methods for submodular maximization. Advances in Neural Information Processing Systems, 5843–5853.Google Scholar
• Nemhauser GL, Wolsey LA, Fisher ML (1978) An analysis of approximations for maximizing submodular set functions–I. Math. Programming 14(1):265–294.Google Scholar
• Niazadeh R, Roughgarden T, Wang JR (2020) Optimal algorithms for continuous non-monotone submodular and DR-submodular maximization. J. Machine Learn. Res. 21(125):1–31.Google Scholar
• Nishio T, Yonetani R (2018) Client selection for federated learning with heterogeneous resources in mobile edge. Preprint, submitted April 23, https://arxiv.org/abs/1804.08333.Google Scholar
• Qian C, Shi J-C, Yu Y, Tang K (2017a) On subset selection with general cost constraints. Internat. Joint Conf. Artificial Intelligence, 2613–2619.Google Scholar
• Qian C, Shi J-C, Yu Y, Tang K, Zhou Z-H. (2017b) Subset selection under noise. Guyon I, Luxburg UV, Bengio S, Wallach H, Fergus R, Vishwanathan S, Garnett R, eds. Advances in Neural Information Processing Systems, vol. 30 (Curran Associates, Inc.).Google Scholar
• Sarkar UK, Chakrabarti PP, Ghose S, De Sarkar SC (1992) A simple 0.5-bounded greedy algorithm for the 0/1 knapsack problem. Inform. Processing Lett. 42(3):173–177.Google Scholar
• Sekar S, Vojnovic M, Yun S-Y (2020) A test score based approach to stochastic submodular optimization. Management Sci. 67(2):1075–1092.Google Scholar
• Singla A, Tschiatschek S, Krause A (2020) Noisy submodular maximization via adaptive sampling with applications to crowdsourced image collection summarization. AAAI Conf. Artificial Intelligence, 2037–2043.Google Scholar
• Soma T, Yoshida Y. (2015) A generalization of submodular cover via the diminishing return property on the integer lattice. Cortes C, Lawrence N, Lee D, Sugiyama M, Garnett R, eds. Advances in Neural Information Processing Systems, vol. 28 (Curran Associates, Inc.).Google Scholar
• Sviridenko M (2004) A note on maximizing a submodular set function subject to a knapsack constraint. Oper. Res. Lett. 32(1):41–43.Google Scholar
• Topkis DM (1978) Minimizing a submodular function on a lattice. Oper. Res. 26(2):305–321.Link, Google Scholar
• Tschiatschek S, Iyer R, Wei H, Bilmes J (2014) Learning mixtures of submodular functions for image collection summarization. Advances in Neural Information Processing Systems, 1413–1421.Google Scholar
• Vondrák J, Chekuri C, Zenklusen R (2011) Submodular function maximization via the multilinear relaxation and contention resolution schemes. ACM Sympos. Theory Comput., 783–792.Google Scholar
• Wei K, Iyer R, Bilmes J (2015) Submodularity in data subset selection and active learning. Internat. Conf. Machine Learn., 1954–1963.Google Scholar
• Wei K, Liu Y, Kirchhoff K, Bartels C, Bilmes J (2014) Submodular subset selection for large-scale speech training data. IEEE Internat. Conf. Acoustics Speech Signal Processing, 3311–3315.Google Scholar
• Yoshida Y (2019) Maximizing a monotone submodular function with a bounded curvature under a knapsack constraint. SIAM J. Discrete Math. 33(3):1452–1471.Google Scholar
• Yu Q, Xu EL, Cui S (2016) Streaming algorithms for news and scientific literature recommendation: Submodular maximization with a d-knapsack constraint. IEEE Global Conf. Signal Inform. Processing, 1295–1299.Google Scholar
• Zhou Y, Chakrabarty D, Lukose R (2008) Budget constrained bidding in keyword auctions and online knapsack problems. Internat. Workshop Internet Network Econom., 566–576.Google Scholar