A Test Score-Based Approach to Stochastic Submodular Optimization

References

• Adomavicius G, Tuzhilin A (2005) Toward the next generation of recommender systems: A survey of the state-of-the-art and possible extensions. IEEE Trans. Knowledge Data Engrg. 17(6):734–749.Crossref, Google Scholar
• Agrawal S, Zadimoghaddam M, Mirrokni V (2018) Proportional allocation: Simple, distributed, and diverse matching with high entropy. Dy JG, Krause A, eds. Proc. 35th Internat. Conf. Machine Learn. 80:99–108.Google Scholar
• Agarwal D, Chen BC, Elango P, Motgi N, Park ST, Ramakrishnan R, Roy S, Zachariah J (2008) Online models for content optimization. Koller D, Schuurmans D, Bengio Y, Bottou L, eds. Advances in Neural Information Processing Systems, vol. 21 (Curran Associates, Red Hook, NY), 17–24.Google Scholar
• Ahmed S, Atamtürk A (2011) Maximizing a class of submodular utility functions. Math. Programming 128(1):149–169.Crossref, Google Scholar
• Asadpour A, Nazerzadeh H (2016) Maximizing stochastic monotone submodular functions. Management Sci. 62(8):2374–2391.Link, Google Scholar
• Asadpour A, Nazerzadeh H, Saberi A (2008) Stochastic submodular maximization. Papadimitriou C, Zhang S, eds. Internat. Workshop Internet Network Econom. (WINE) (Springer, Berlin, Heidelberg), 477–489.Google Scholar
• Badanidiyuru A, Vondrák J (2014) Fast algorithms for maximizing submodular functions. Chekuri C, ed. Proc. 25th Annual ACM-SIAM Sympos. Discrete Algorithms, (Society for Industrial and Applied Mathematics, Philadelphia) 1497–1514.Google Scholar
• Balcan MF, Harvey NJA (2011) Learning submodular functions. Proc. 43rd ACM Sympos. Theory Comput., STOC 2011 (Association for Computing Machinery, New York), 793–802.Google Scholar
• Balkanski E, Rubinstein A, Singer Y (2019) An exponential speedup in parallel running time for submodular maximization without loss in approximation. Chan T, ed. Proc. 30th Annual ACM-SIAM Sympos. Discrete Algorithms (Society for Industrial and Applied Mathematics, Philadelphia), 283–302.Google Scholar
• Besbes O, Gur Y, Zeevi A (2015) Optimization in online content recommendation services: Beyond click-through rates. Manufacturing Service Oper. Management 18(1):15–33.Link, Google Scholar
• Bhowmik A, Borkar V, Garg D, Pallan M (2014) Submodularity in team formation problem. Zaki M, Obradovic Z, Tan PN, Banerjee A, Kamath C, Parthasarathy S, eds. Proc. 2014 SIAM Internat. Conf. Data Mining (Society for Industrial and Applied Mathematics, Philadelphia), 893–901.Google Scholar
• Calinescu G, Chekuri C, Pál M, Vondrák J (2011) Maximizing a monotone submodular function subject to a matroid constraint. SIAM J. Comput. 40(6):1740–1766.Crossref, Google Scholar
• Chien CF (2002) A portfolio–evaluation framework for selecting R&D projects. R&D Management 32(4):359–368.Crossref, Google Scholar
• Cohavi K, Dobzinski S (2017) Faster and simpler sketches of valuation functions. ACM Trans. Algorithms 13(3):30:1–30:9.Google Scholar
• Cohen MC, Keller PW, Mirrokni V, Zadimoghaddam M (2019) Overcommitment in cloud services: Bin packing with chance constraints. Management Sci. 65(7):3255–3271.Link, Google Scholar
• Danaher PJ, Lee J, Kerbache L (2010) Optimal Internet media selection. Marketing Sci. 29(2):336–347.Link, Google Scholar
• Dixit AK, Stiglitz JE (1977) Monopolistic competition and optimum product diversity. Amer. Econom. Rev. 67(3):297–308.Google Scholar
• Ene A, Nguyen HL (2019) Submodular maximization with nearly-optimal approximation and adaptivity in nearly-linear time. Chan T, ed. Proc. 30th Annual ACM-SIAM Sympos. Discrete Algorithms (Society for Industrial and Applied Mathematics, Philadelphia), 274–282.Google Scholar
• Feige U (1998) A threshold of ln n for approximating set cover. J. ACM 45(4):634–652.Crossref, Google Scholar
• Feldman V, Vondrák J (2014) Optimal bounds on approximation of submodular and XOS functions by juntas. SIAM J. Comput. 45(3):1129–1170.Google Scholar
• Feldman M, Zenklusen R (2018) The submodular secretary problem goes linear. SIAM J. Comput. 47(2):330–366.Crossref, Google Scholar
• Fu R, Subramanian A, Venkateswaran A (2016) Project characteristics, incentives, and team production. Management Sci. 62(3):785–801.Link, Google Scholar
• Goel A, Guha S, Munagala K (2006) Asking the right questions: Model-driven optimization using probes. Proc. 25th ACM SIGMOD-SIGACT-SIGART Sympos. Principles Database Systems (Association for Computing Machinery, New York), 203–212.Google Scholar
• Goemans MX, Harvey NJA, Iwata S, Mirrokni V (2009) Approximating submodular functions everywhere. Mathieu C, ed. Proc. 20th Annual ACM-SIAM Sympos. Discrete Algorithms (Society for Industrial and Applied Mathematics, Philadelphia), 535–544.Google Scholar
• Gotovos A, Hassani SH, Krause A (2015) Sampling from probabilistic submodular models. Cortes C, Lee DD, Sugiyama M, Garnett R, eds. Advances in Neural Information Processing Systems, vol. 28 (Curran Associates, Red Hook, NY), 1945–1953.Google Scholar
• Hassidim A, Singer Y (2017) Submodular optimization under noise. Kale S, Shamir O, eds. COLT 2017 Proc. Machine Learn. Res. 65:1069–1122.Google Scholar
• Henriksen AD, Traynor AJ (1999) A practical R&D project-selection scoring tool. IEEE Trans. Engrg. Management 46(2):158–170.Crossref, Google Scholar
• Herbrich R, Minka T, Graepel T (2006) TrueskillTM: A Bayesian skill rating system. Schölkopf B, Platt JC, Hoffman T, eds. Advances in Neural Information Processing Systems, vol. 19 (Curran Associates, Red Hook, NY), 569–576.Google Scholar
• Iyer R, Bilmes J (2013) Submodular optimization with submodular cover and submodular knapsack constraints. Burges, CJC, Bottou L, Welling M, Ghahramani Z, Weinberger KQ, eds. Advances in Neural Information Processing Systems, vol. 26 (Curran Associates, Red Hook, NY), 2436–2444.Google Scholar
• Kempe D, Kleinberg JM, Tardos É (2015) Maximizing the spread of influence through a social network. Theory Comput. 11(4):105–147.Crossref, Google Scholar
• Kleinberg J, Raghu M (2018) Team performance with test scores. ACM Trans. Econom. Comput. 6(3–4):17–26.Google Scholar
• Kleinberg JM, Oren S (2011) Mechanisms for (mis)allocating scientific credit. Fortnow L, Vadhan S, eds. Proc. 43rd ACM Sympos. Theory Comput., STOC 2011 (Association for Computing Machinery, New York), 529–538.Google Scholar
• Kleywegt A, Shapiro A, Homem-de Mello T (2002) The sample average approximation method for stochastic discrete optimization. SIAM J. Optim. 12(2):479–502.Crossref, Google Scholar
• Koç A, Morton DP (2014) Prioritization via stochastic optimization. Management Sci. 61(3):586–603.Link, Google Scholar
• Korula N, Mirrokni V, Zadimoghaddam M (2018) Online submodular welfare maximization: Greedy beats 1/2 in random order. SIAM J. Comput. 47(3):1056–1086.Crossref, Google Scholar
• Krause A, Golovin D (2014) Submodular Function Maximization (Cambridge University Press, Cambridge, UK), 71–104.Google Scholar
• Lehmann B, Lehmann D, Nisan N (2006) Combinatorial auctions with decreasing marginal utilities. Games Econom. Behav. 55(2):270–296.Crossref, Google Scholar
• Li H (2011) Learning to Rank for Information Retrieval and Natural Language Processing (Morgan & Claypool, San Rafael, CA).Crossref, Google Scholar
• Manning C, Raghavan P, Schütze H (2010) Introduction to information retrieval. Natl. Language Engrg. 16(1):100–103.Google Scholar
• Mehta A (2013) Online matching and ad allocation. Foundations Trends Theoret. Comput. Sci. 8(4):265–368.Google Scholar
• Nemhauser G, Wolsey L, Fisher M (1978) An analysis of approximations for maximizing submodular set functions—I. Math. Programming 14(1):265–294.Crossref, Google Scholar
• Paulson C, Luo L, James GM (2018) Efficient large-scale Internet media selection optimization for online display advertising. J. Marketing Res. 55(4):489–506.Crossref, Google Scholar
• Shapiro A, Nemirovski A (2005) On the complexity of stochastic programming problems. Jeyakumar V, Rubinov AM, eds. Continuous Optimization Current Trends and Modern Applications (Springer, Boston), 111–146.Google Scholar
• Singla A, Tschiatschek S, Krause A (2016) Noisy submodular maximization via adaptive sampling with applications to crowdsourced image collection summarization. Proc. 30th AAAI Conf. Artificial Intelligence (AAAI Press, Palo Alto, CA), 2037–2043.Google Scholar
• Sviridenko M, Vondrák J, Ward J (2017) Optimal approximation for submodular and supermodular optimization with bounded curvature. Math. Oper. Res. 42(4):1197–1218.Link, Google Scholar
• Swamy C, Shmoys DB (2012) Sampling-based approximation algorithms for multistage stochastic optimization. SIAM J. Comput. 41(4):975–1004.Crossref, Google Scholar
• Vondrak J (2008) Optimal approximation for the submodular welfare problem in the value oracle model. Proc. 40th Annual ACM Sympos. Theory Comput. (Association for Computing Machinery, New York), 67–74.Google Scholar
• Yuan R, Zhao L, Wang W (2007) Cooperation and competition dynamics in an online game community. Schuler D, ed. Internat. Conf. Online Communities Soc. Comput. (Springer, Berlin, Heidelberg), 475–484.Google Scholar