Maximizing Sequence-Submodular Functions and Its Application to Online Advertising

References

• Adamczyk M , Sviridenko M , Ward J (2016) Submodular stochastic probing on matroids. Math. Oper. Res. 41(3):1022–1038.Link, Google Scholar
• Agrawal R , Gupta A , Prabhu Y , Varma M (2013) Multi-label learning with millions of labels: Recommending advertiser bid phrases for web pages. Proc. Internat. Conf. World Wide Web (ACM New York), 13–24.Google Scholar
• Andelman N , Mansour Y (2004) Auctions with budget constraints. Hagerup T, Katajainen J, eds. Algorithm Theory - SWAT 2004. SWAT 2004. Lecture Notes in Computer Science (vol 3111. Springer, Berlin, Heidelberg).Google Scholar
• Asadpour A , Nazerzadeh H (2015) Maximizing stochastic monotone submodular functions. Management Sci. 62(8):2374–2391.Link, Google Scholar
• Asadpour A , Wang X , Zhang J (2020) Online resource allocation with limited flexibility. Management Sci. 66(2):642–666.Link, Google Scholar
• Balkanski E , Singer Y (2018) Approximation guarantees for adaptive sampling. Dy J, Krause A, eds. Internat. Conf. Machine Learn. (PMLR, Stockholm, Sweden), 393–402.Google Scholar
• Balseiro SR , Candogan O (2017) Optimal contracts for intermediaries in online advertising. Oper. Res. 65(4):878–896.Link, Google Scholar
• Dobzinski S , Schapira M (2006) An improved approximation algorithm for combinatorial auctions with submodular bidders. Proc. Annual ACM-SIAM Sympos. Discrete Algorithms (SIAM, Philadelphia), 1064–1073.Google Scholar
• Feige U (2009) On maximizing welfare when utility functions are subadditive. SIAM J. Comput. 39(1):122–142.Crossref, Google Scholar
• Feige U , Mirrokni VS , Vondrak J (2011) Maximizing non-monotone submodular functions. SIAM J. Comput. 40(4):1133–1153.Crossref, Google Scholar
• Feldman M , Harshaw C , Karbasi A (2017) Greed is good: Near-optimal submodular maximization via greedy optimization. Preprint, submitted April 5, https://arxiv.org/abs/1704.01652.Google Scholar
• Feldman M , Karbasi A , Kazemi E (2018) Do less, get more: Streaming submodular maximization with subsampling. Adv. Neural Inform. Processing Systems 31:732–742.Google Scholar
• Fleischer L , Goemans MX , Mirrokni VS , Sviridenko M (2006) Tight approximation algorithms for maximum general assignment problems. Proc. Annual ACM-SIAM Sympos. Discrete Algorithms (SIAM, Philadelphia), 611–620.Google Scholar
• Gabillon V , Kveton B , Wen Z , Eriksson B , Muthukrishnan S (2013) Adaptive submodular maximization in bandit setting. Burges CJC, Bottou L, Welling M, Ghahrahmani Z, Weinberger KQ, eds. Advances in Neural Information Processing Systems (Curran Associates, Red Hook, NY), 2697–2705.Google Scholar
• Goel G , Mehta A (2008) Online budgeted matching in random input models with applications to adwords. Proc. Annual ACM-SIAM Sympos. Discrete Algorithms (SIAM, Philadelphia), 982–991.Google Scholar
• Golovin D , Krause A (2011) Adaptive submodularity: Theory and applications in active learning and stochastic optimization. J. Artificial Intelligence Res. 42:427–486.Google Scholar
• Goundan PR , Schulz AS (2007) Revisiting the greedy approach to submodular set function maximization. Working paper, Massachusetts Institute of Technology, Cambridge, MA.Google Scholar
• Jones R , Rey B , Madani O , Greiner W (2006) Generating query substitutions. Proc. Internat. Conf. World Wide Web (ACM, New York), 387–396.Google Scholar
• Karp RM , Vazirani UV , Vazirani VV (1990) An optimal algorithm for on-line bipartite matching. Proc. Annual ACM Sympos. Theory Comput. (ACM, New York), 352–358.Google Scholar
• Kempe D , Kleinberg J , Tardos É (2003) Maximizing the spread of influence through a social network. Proc. ACM SIGKDD Internat. Conf. Knowledge Discovery Data Mining (ACM, New York), 137–146.Google Scholar
• Khot S , Lipton RJ , Markakis E , Mehta A (2005) Inapproximability results for combinatorial auctions with submodular utility functions. Internat. Workshop Internet Network Econom. (Springer, Berlin), 92–101.Google Scholar
• Lahaie S , Pennock D , Saberi A , Vohra R (2007) Algorithmic game theory, chapter sponsored search (Cambridge University Press, Cambridge, UK).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 P , Milenkovic O (2017) Inhomogeneous hypergraph clustering with applications. Guyon I, von Luxburg U, Wallach HM, Fergus R, Vishwanathan SVN, eds. Advances in Neural Information Processing Systems, 2305–2315.Google Scholar
• Lin H , Bilmes J (2011) A class of submodular functions for document summarization. Proc. Annual Meeting Assoc. Comput. Linguistics: Human Language Tech. (ACM, New York), vol. 1, 510–520.Google Scholar
• Malekian A , Chang C-C , Kumar R , Wang G (2008) Optimizing query rewrites for keyword-based advertising. Proc. ACM Conf. Electronic Commerce (ACM, New York), 10–19.Google Scholar
• Mehta A (2013) Online matching and ad allocation. Foundations Trends Theoret. Comput. Sci. 8(4):265–368.Google Scholar
• Mehta A , Waggoner B , Zadimoghaddam M (2015) Online stochastic matching with unequal probabilities. Proc. Annual ACM-SIAM Sympos. Discrete Algorithms (SIAM, Philadelphia), 1388–1404.Google Scholar
• Mehta A , Saberi A , Vazirani U , Vazirani V (2007) Adwords and generalized online matching. J. ACM 54(5):22.Crossref, Google Scholar
• Mirzasoleiman B , Karbasi A , Sarkar R , Krause A (2016) Distributed submodular maximization. J. Machine Learn. Res. 17(238):1–44.Google Scholar
• Mitrovic M , Feldman M , Krause A , Karbasi A (2018) Submodularity on hypergraphs: From sets to sequences. Storkey A, Perez-Cruz F, eds. Proc. Machine Learn. Res. (PMLR), 1177–1184.Google Scholar
• Mossel E , Roch S (2010) Submodularity of influence in social networks: From local to global. SIAM J. Comput. 39(6):2176–2188.Crossref, Google Scholar
• Nemhauser GL , Wolsey LA (1978) Best algorithms for approximating the maximum of a submodular set function. Math. Oper. Res. 3(3):177–188.Link, Google Scholar
• Nemhauser GL , Wolsey LA , Fisher ML (1978) An analysis of approximations for maximizing submodular set functions. Math. Programming 14(1):265–294.Crossref, Google Scholar
• Singh G , Parikh N , Sundaresan N (2012) Rewriting null e-commerce queries to recommend products. Proc. Internat. Conf. World Wide Web (ACM, New York), 73–82. Google Scholar
• Singla A , Bogunovic I , Bartók G , Karbasi A , Krause A (2014) Near-optimally teaching the crowd to classify. Proc. Internat. Conf. Machine Learn., vol. 32, 154–162.Google Scholar
• Stavrogiannis LC , Gerding EH , Polukarov M (2014) Auction mechanisms for demand-side intermediaries in online advertising exchanges. Proc. Internat. Conf. Autonomous Agents Multi-Agent Systems (International Foundation for Autonomous Agents and Multiagent Systems, Richland, SC), 1037–1044.Google Scholar
• Tschiatschek S , Singla A , Krause A Selecting sequences of items via submodular maximization. Proc. 2017 Assoc. Advancement Artificial Intelligence (AAAI Press), 2667–2673.Google Scholar
• Vondrák J (2008) Optimal approximation for the submodular welfare problem in the value oracle model. Proc. Annual ACM Sympos. Theory of Comput. (ACM, New York), 67–74.Google Scholar
• Wolsey LA (1982) Maximising real-valued submodular functions: Primal and dual heuristics for location problems. Math. Oper. Res. 7(3):410–425.Link, Google Scholar
• Yan S , Lin W , Wu T , Xiao D , Zheng X , Wu B , Liu K (2018) Beyond keywords and relevance: A personalized ad retrieval framework in e-commerce sponsored search. Proc. World Wide Web Conf. (International World Wide Web Conferences Steering Committee, Geneva, Switzerland), 1919–1928.Google Scholar
• Zhang WV , Jones R (2007) Comparing click logs and editorial labels for training query rewriting. Amitay E, Murray CG, Teevan J, eds. Query Log Analysis: Social Technological Challenges Workshop 16th Internat. World Wide Web Conf. Google Scholar
• Zhang Z , Chong EKP , Pezeshki A , Moran W (2015) String submodular functions with curvature constraints. IEEE Trans. Automatic Controls 61(3):601–616.Crossref, Google Scholar
• Zhang Z , Chong EKP , Pezeshki A , Moran W , Howard SD (2012) Submodularity and optimality of fusion rules in balanced binary relay trees. 51st IEEE Conf. Decision Control (IEEE, Piscataway, NJ), 3802–3807.Google Scholar