An Optimal Streaming Algorithm for Submodular Maximization with a Cardinality Constraint

References

• [1] Alaluf N, Ene A, Feldman M, Nguyen HL, Suh A (2020) Optimal streaming algorithms for submodular maximization with cardinality constraints. Czumaj A, Dawar A, Merelli E, eds. Proc. 47th Internat. Colloquium on Automata, Languages, and Programming ICALP (Schloss Dagstuhl - Leibniz-Zentrum für Informatik), 6:1–6:19.Google Scholar
• [2] Alaluf N, Ene A, Feldman M, Nguyen HL, Suh A (2020) Optimal streaming algorithms for submodular maximization with cardinality constraints. Preprint, submitted February 20, https://arxiv.org/abs/1911.12959v2.Google Scholar
• [3] Azar Y, Gamzu I, Roth R (2011) Submodular max-sat. Demetrescu C, Halldórsson M, eds. Proc. 19th Annual European Sympos. ESA (Springer), 323–334.Google Scholar
• [4] Badanidiyuru A, Mirzasoleiman B, Karbasi A, Krause A (2014) Streaming submodular maximization: Massive data summarization on the fly. Macskassy SA, Perlich C, Leskovec J, Wang W, Ghani R, eds. Proc. 20th ACM SIGKDD Internat. Conf. Knowledge Discovery and Data Mining (ACM), 671–680.Google Scholar
• [5] Barbosa R, Ene A, Nguyen HL, Ward J (2015) The power of randomization: Distributed submodular maximization on massive datasets. Bach FR, Blei DM, eds. Proc. 32nd Internat. Conf. Machine Learn. ICML (JMLR.org), 1236–1244.Google Scholar
• [6] Barbosa R, Ene A, Nguyen HL, Ward J (2016) A new framework for distributed submodular maximization. Dinur I, ed. Proc. 57th Annual Sympos. Foundations of Comput. Sci. (FOCS) (IEEE Computer Society), 645–654.Google Scholar
• [7] Buchbinder N, Feldman M (2018) Deterministic algorithms for submodular maximization problems. ACM Trans. Algorithms 14(3):32:1–32:20.Crossref, Google Scholar
• [8] Buchbinder N, Feldman M (2019) Constrained submodular maximization via a non-symmetric technique. Math. Oper. Res. 44(3):988–1005.Link, Google Scholar
• [9] Buchbinder N, Feldman M, Garg M (2019) Deterministic (1/2+ε)-approximation for submodular maximization over a matroid. Chan TM, ed. Proc. 13th Annual Sympos. Discrete Algorithms (SODA) (SIAM), 241–254.Google Scholar
• [10] Buchbinder N, Feldman M, Schwartz R (2019) Online submodular maximization with preemption. ACM Trans. Algorithms 15(3):30:1–30:31.Crossref, Google Scholar
• [11] Buchbinder N, Feldman M, Filmus Y, Garg M (2020) Online submodular maximization: Beating 1/2 made simple. Math. Programming 183(1):149–169.Crossref, Google Scholar
• [12] Buchbinder N, Feldman M, Naor J, Schwartz R (2014) Submodular maximization with cardinality constraints. Chekuri C, ed. Proc. 25th Annual Sympos. Discrete Algorithms (SODA) (SIAM), 1433–1452.Google Scholar
• [13] 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
• [14] Chakrabarti A, Kale S (2015) Submodular maximization meets streaming: Matchings, matroids, and more. Math. Programming 154(1–2):225–247.Crossref, Google Scholar
• [15] Chan TH, Huang Z, Jiang SH, Kang N, Tang ZG (2018) Online submodular maximization with free disposal. ACM Trans. Algorithms 14(4):56:1–56:29.Crossref, Google Scholar
• [16] Chekuri C (2018) Personal communication. The communication took place over e-mail on February 8, 2018.Google Scholar
• [17] Chekuri C, Gupta S, Quanrud K (2015) Streaming algorithms for submodular function maximization. Halldórsson MM, Iwama K, Kobayashi N, Speckmann B, eds. Proc. 42nd Internat. Colloquium Automata Languages Programming (Springer), 318–330.Google Scholar
• [18] Chekuri C, Vondrák J, Zenklusen R (2010) Dependent randomized rounding via exchange properties of combinatorial structures. Proc. 51st Annual Sympos. Foundations of Comput. Sci. (FOCS) (IEEE Computer Society), 575–584.Google Scholar
• [19] 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
• [20] Ene A, Nguyen HL (2016) Constrained submodular maximization: Beyond 1/e. Dinur I, ed. Proc. 57th Annual Sympos. on Foundations of Computer Sci. (FOCS) (IEEE Computer Society), 248–257.Google Scholar
• [21] Epasto A, Mirrokni V, Zadimoghaddam M (2017) Bicriteria distributed submodular maximization in a few rounds. Scheideler C, Taghi Hajiaghayi M, eds. Proc. 29th Sympos. Parallelism in Algorithms and Architectures (SPAA) (ACM), 25–33.Google Scholar
• [22] Feige U, Mirrokni VS, Vondrák J (2011) Maximizing non-monotone submodular functions. SIAM J. Comput. 40(4):1133–1153.Crossref, Google Scholar
• [23] Feldman M (2017) Maximizing symmetric submodular functions. ACM Trans. Algorithms 13(3):39:1–39:36.Crossref, Google Scholar
• [24] Feldman M, Harshaw C, Karbasi A (2017) Greed is good: Near-optimal submodular maximization via greedy optimization. Kale S, Shamir O, eds. Proc. Machine Learn. Research 65 (COLT 2017) (PMLR), 758–784.Google Scholar
• [25] Feldman M, Karbasi A, Kazemi E (2018) Do less, get more: Streaming submodular maximization with subsampling. Bengio S, Wallach HM, Larochelle H, Grauman K, Cesa-Bianchi N, Garnett R, eds. Proc. Annual Conf. Neural Inform. Processing Systems, 732–742.Google Scholar
• [26] Feldman M, Naor JS, Schwartz R (2011) A unified continuous greedy algorithm for submodular maximization. Ostrovsky R, ed. Proc. IEEE 52nd Annual Sympos. Foundations of Comput. Sci. (FOCS) (IEEE Computer Society), 570–579.Google Scholar
• [27] Feldman M, Norouzi-Fard A, Svensson O, Zenklusen R (2020) The one-way communication complexity of submodular maximization with applications to streaming and robustness. Makarychev K, Makarychev Y, Tulsiani M, Kamath G, Chuzhoy J, eds. Proc. 52nd Annual (SIGACT) Sympos. Theory of Comput. (STOC) (ACM), 1363–1374.Google Scholar
• [28] 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
• [29] Gharan SO, Vondrák J (2011) Submodular maximization by simulated annealing. Randall D, ed. Proc. 22nd Annual Sympos. Discrete Algorithms (SODA) (SIAM).Google Scholar
• [30] Kapralov M, Post I, Vondrák J (2013) Online submodular welfare maximization: Greedy is optimal. Khanna S, ed. Proc. 24th Annual Sympos. Discrete Algorithms (SODA) (SIAM), 1216–1225.Google Scholar
• [31] 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. Chaudhuri K, Salakhutdinov R, eds. Proc. 36th Internat. Conf. Machine Learn. (ICML) (PMLR), 3311–3320.Google Scholar
• [32] Korula N, Mirrokni VS, Zadimoghaddam M (2018) Online submodular welfare maximization: Greedy beats 1/2 in random order. SIAM J. Comput. 47(3):1056–1086.Crossref, Google Scholar
• [33] Kumar R, Moseley B, Vassilvitskii S, Vattani A (2015) Fast greedy algorithms in mapreduce and streaming. ACM Trans. Parallel Comput. 2(3):14:1–14:22.Google Scholar
• [34] 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
• [35] Lee J, Mirrokni VS, Nagarajan V, Sviridenko M (2009) Non-monotone submodular maximization under matroid and knapsack constraints. Mitzenmacher M, ed. Proc. 41st Annual Sympos. Theory Comput. (STOC) (ACM), 323–332.Google Scholar
• [36] Lovász L (1982) Submodular functions and convexity. Math. Programming State Art, XIth Internat. Sympos. Math. Programming, 235–257.Google Scholar
• [37] Mirrokni V, Zadimoghaddam M (2015) Randomized composable core-sets for distributed submodular maximization. Servedio RA, Rubinfeld R, eds. Proc. 47th Annual Sympos. Theory Comput. (STOC) (ACM).Google Scholar
• [38] Mirzasoleiman B, Jegelka S, Krause A (2018) Streaming non-monotone submodular maximization: Personalized video summarization on the fly. McIlraith SA, Weinberger KQ, eds. Proc. 32nd Conf. Artificial Intelligence (AAAI) (AAAI Press), 1379–1386.Google Scholar
• [39] Mirzasoleiman B, Karbasi A, Badanidiyuru A, Krause A (2015) Distributed submodular cover: Succinctly summarizing massive data. Cortes C, Lawrence ND, Lee DD, Sugiyama M, Garnett R, eds. Proc. Annual Conf. Neural Informat. Processing Systems (NIPS) 28:2881–2889.Google Scholar
• [40] 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. 27th Annual Conf. Neural Informat. Processing Systems (NIPS), 2049–2057.Google Scholar
• [41] 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
• [42] 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
• [43] Norouzi-Fard A, Tarnawski J, Mitrovic S, Zandieh A, Mousavifar A, Svensson O (2018) Beyond 1/2-approximation for submodular maximization on massive data streams. Dy JG, Krause A, eds. Proc. 35th Internat. Conf. Machine Learn. (ICML) (PMLR), 3826–3835.Google Scholar
• [44] Vondrák J (2013) Symmetry and approximability of submodular maximization problems. SIAM J. Comput. 42(1):265–304.Crossref, Google Scholar