Submodular Maximization Through the Lens of Linear Programming

References

• [1] Ageev AA, Sviridenko M (2004) Pipage rounding: A new method of constructing algorithms with proven performance guarantee. J. Combin. Optim. 8(3):307–328.Crossref, Google Scholar
• [2] Balcan MF, Blum A, Mansour Y (2008) Item pricing for revenue maximization. Fortnow L, Riedl J, Sandholm T, eds. Proc. 9th ACM Conf. Electronic Commerce (EC) (ACM, New York), 50–59.Crossref, Google Scholar
• [3] Buchbinder N, Feldman M (2019) Constrained submodular maximization via a non-symmetric technique. Math. Oper. Res., ePub ahead of print May 17, https://pubsonline.informs.org/doi/10.1287/moor.2018.0955.Link, Google Scholar
• [4] Buchbinder N, Feldman M (2016) Deterministic algorithms for submodular maximization problems. Krauthgamer R, ed. Proc. 27th Annual ACM-SIAM Sympos. Discrete Algorithms (SODA) (Society for Industrial and Applied Mathematics, Philadelphia), 392–403.Crossref, Google Scholar
• [5] Buchbinder N, Feldman M, Naor JS, Schwartz R (2012) A tight linear time (1/2)-approximation for unconstrained submodular maximization. Proc. 53rd Annual IEEE Sympos. Foundations Comput. Sci. (FOCS) (IEEE Computer Society, Washington, DC), 649–658.Google Scholar
• [6] Buchbinder N, Feldman M, Naor JS, Schwartz R (2015) A tight linear time (1/2)-approximation for unconstrained submodular maximization. SIAM J. Comput. 44(5):1384–1402.Crossref, Google Scholar
• [7] Călinescu 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
• [8] Chekuri C, Vondrák J, Zenklusen R (2009) Dependent randomized rounding for matroid polytopes and applications. Working paper, University of Illinois at Urbana–Champaign, Champaign.Google Scholar
• [9] Chekuri C, Vondrák J, Zenklusen R (2010) Dependent randomized rounding via exchange properties of combinatorial structures. Proc. 51st Annual IEEE Sympos. Foundations Comput. Sci. (FOCS) (IEEE Computer Society, Washington, DC), 575–584.Crossref, Google Scholar
• [10] Chekuri C, Vondrák J, Zenklusen R (2011) Multi-budgeted matchings and matroid intersection via dependent rounding. Randall D, ed. Proc. 22nd Annual ACM-SIAM Sympos. Discrete Algorithms (SODA) (Society for Industrial and Applied Mathematics, Philadelphia), 1080–1097.Crossref, Google Scholar
• [11] Chekuri C, Vondrák J, Zenklusen R (2011) Submodular function maximization via the multilinear relaxation and contention resolution schemes. Fortnow L, Vadhan SP, eds. Proc. 43rd Annual ACM Sympos. Theory Comput. (STOC) (ACM, New York), 783–792.Google Scholar
• [12] Chekuri C, Vondrák J, Zenklusen R (2014) Submodular function maximization via the multilinear relaxation and contention resolution schemes. SIAM J. Comput. 43(6):1831–1879.Crossref, Google Scholar
• [13] 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.Crossref, Google Scholar
• [14] Ene A, Nguy\tilde{\hat{{\mathrm e}}}n HL (2016) Constrained submodular maximization: Beyond 1/e. Dinur I, ed. Proc. 57th Annual IEEE Sympos. Foundations Comput. Sci. (FOCS) (IEEE Computer Society, Washington, DC), 248–257.Crossref, Google Scholar
• [15] Feige U, Mirrokni VS, Vondrák J (2007) Maximizing non-monotone submodular functions. Proc. 48th Annual IEEE Sympos. Foundations Comput. Sci. (FOCS) (IEEE Computer Society, Washington, DC), 461–471.Crossref, Google Scholar
• [16] Feige U, Mirrokni VS, Vondrák J (2011) Maximizing non-monotone submodular functions. SIAM J. Comput. 40(4):1133–1153.Crossref, Google Scholar
• [17] Feldman M (2013) Maximization problems with submodular objective functions. PhD thesis, Computer Science Department, Technion—Israel Institute of Technology, Haifa.Google Scholar
• [18] Feldman M, Zenklusen R (2015) The submodular secretary problem goes linear. Guruswami V, ed. Proc. 56th Annual IEEE Sympos. Foundations Comput. Sci. (FOCS) (IEEE Computer Society, Washington, DC), 486–505.Crossref, Google Scholar
• [19] Feldman M, Harshaw C, Karbasi A (2017) Greed is good: Near-optimal submodular maximization via greedy optimization. Proc. Machine Learn. Res. 65:758–784.Google Scholar
• [20] Feldman M, Naor JS, Schwartz R (2011) Nonmonotone submodular maximization via a structural continuous greedy algorithm. Aceto L, Henzinger M, Sgall J, eds. Proc. 38th Internat. Colloquium Automata Languages Programming (ICALP) (Springer, Berlin, Heidelberg), 342–353.Crossref, Google Scholar
• [21] Feldman M, Naor JS, Schwartz R (2011) A unified continuous greedy algorithm for submodular maximization. Ostrovsky R, ed. Proc. 52nd Annual IEEE Sympos. Foundations Comput. Sci. (FOCS) (IEEE Computer Society, Washington, DC), 570–579.Crossref, Google Scholar
• [22] Feldman M, Naor JS, Schwartz R, Ward J (2011) Improved approximations for k-exchange systems. Demetrescu C, Halldórsson MM, eds. Proc. 19th Annual Eur. Sympos. Algorithms (ESA) (Springer, Berlin, Heidelberg), 784–798.Google Scholar
• [23] Fisher ML, Nemhauser GL, Wolsey LA (1978) An analysis of approximations for maximizing submodular set functions—II. Math. Programming Stud. 8:73–87.Crossref, Google Scholar
• [24] Gupta A, Roth A, Schoenebeck G, Talwar K (2010) Constrained non-monotone submodular maximization: Offline and secretary algorithms. Saberi A, ed. Internet Network Economics: 6th Internat. Workshop, WINE 2010, Stanford, CA, December 13—17 (Springer, Berlin, Heidelberg), 246–257.Crossref, Google Scholar
• [25] Hartline J, Mirrokni VS, Sundararajan M (2008) Optimal marketing strategies over social networks. Huai J, Chen R, Hon H-W, Liu Y, Ma W-Y, Tomkins A, Zhang X, eds. Proc. 17th Internat. World Wide Web Conf. (WWW) (ACM, New York), 189–198.Crossref, Google Scholar
• [26] Hazan E, Safra S, Schwartz O (2006) On the complexity of approximating k-set packing. Comput. Complexity 15(1):20–39.Crossref, Google Scholar
• [27] Karp RM (1972) Reducibility among combinatorial problems. Miller RE, Thatcher JW, eds. Complexity Computer Computations: Proc. Sympos. Complexity Comp. Computations, Yorktown Heights, New York, March 20—22 (Plenum Press, New York), 85–103.Crossref, Google Scholar
• [28] Kulik A, Shachnai H, Tamir T (2013) Approximations for monotone and non-monotone submodular maximization with knapsack constraints. Math. Oper. Res. 38(4):729–739.Link, Google Scholar
• [29] Lee J, Sviridenko M, Vondrák J (2010) Submodular maximization over multiple matroids via generalized exchange properties. Math. Oper. Res. 35(4):795–806.Link, Google Scholar
• [30] Lee J, Mirrokni VS, Nagarajan V, Sviridenko M (2009) Non-monotone submodular maximization under matroid and knapsack constraints. Mitzenmacher M, ed. Proc. 41st Annual ACM Sympos. Theory Comput. (STOC) (ACM, New York), 323–332.Crossref, Google Scholar
• [31] Lee J, Mirrokni VS, Nagarajan V, Sviridenko M (2010) Maximizing nonmonotone submodular functions under matroid or knapsack constraints. SIAM J. Discrete Math. 23(4):2053–2078.Crossref, Google Scholar
• [32] Lehman E, Leighton FT, Meyer AR (2017) Mathematics for Computer Science (Samurai Media Limited, Surrey, UK).Google Scholar
• [33] Lehmann B, Lehmann D, Nisan N (2006) Combinatorial auctions with decreasing marginal utilities. Games Econom. Behav. 55(2):270–296.Crossref, Google Scholar
• [34] Mirzasoleiman B, Karbasi A, Sarkar R, Krause A (2013) Distributed submodular maximization: Identifying representative elements in massive data. Burges CJC, Bottou L, Ghahramani Z, Weinberger KQ, eds. Proc. 26th Internat. Conf. Neural Inform. Processing Systems (NIPS) (Curran Associates, Inc., Red Hook, NY), 2049–2057.Google Scholar
• [35] 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
• [36] Nemhauser GL, Wolsey LA, Fisher ML (1978) An analysis of approximations for maximizing submodular set functions–I. Math. Programming 14(1):265–294.Crossref, Google Scholar
• [37] Schrijver A (2003) Combinatorial Optimization: Polyhedra and Efficiency (Springer, Berlin, Heidelberg).Google Scholar
• [38] Sviridenko M (2004) A note on maximizing a submodular set function subject to a knapsack constraint. Oper. Res. Lett. 32(1):41–43.Crossref, Google Scholar
• [39] Vondrák J (2008) Optimal approximation for the submodular welfare problem in the value oracle model. Dwork C, ed. Proc. 40th Annual ACM Sympos. Theory Comput. (STOC) (ACM, New York), 67–74.Crossref, Google Scholar
• [40] Vondrák J (2013) Symmetry and approximability of submodular maximization problems. SIAM J. Comput. 42(1):265–304.Crossref, Google Scholar
• [41] Ward J (2012) A (k+3)/2-approximation algorithm for monotone submodular k-set packing and general k-exchange systems. Dürr C, Wilke T, eds. Proc. 29th Internat. Sympos. Theoret. Aspects Comput. Sci. (STACS) (Schloss Dagstuhl—Leibniz-Zentrum für Informatik, Dagstuhl, Germany), 42–53.Google Scholar
• [42] Wei K, Iyer R, Bilmes J (2014) Fast multi-stage submodular maximization. Proc. Machine Learn. Res. 32(2):1494–1502.Google Scholar