Streaming Submodular Maximization Under Matroid Constraints

References

• [1] Agrawal S, Shadravan M, Stein C (2019) Submodular secretary problem with shortlists. Blum A, ed. 10th Innovations Theoret. Comput. Sci. Conf. (ITCS) (Schloss Dagstuhl – Leibniz-Zentrum für Informatik, Wadern, Germany).Google Scholar
• [2] Badanidiyuru A, Vondrák J (2014) Fast algorithms for maximizing submodular functions. Proc. 25th Annual ACM-SIAM Sympos. Discrete Algorithms (SODA) (SIAM, Philadelphia), 1497–1514.Google Scholar
• [3] Badanidiyuru A, Mirzasoleiman B, Karbasi A, Krause A (2014) Streaming submodular maximization: Massive data summarization on the fly. Proc. 20th ACM Conf. Knowledge Discovery Data Mining (KDD) (ACM, New York), 671–680.Google Scholar
• [4] Buchbinder N, Feldman M (2019) Constrained submodular maximization via a nonsymmetric technique. Math. Oper. Res. 44(3):988–1005.Link, Google Scholar
• [5] Buchbinder N, Feldman M, Naor J, Schwartz R (2014) Submodular maximization with cardinality constraints. Chekuri C, ed. Proc. Twenty-Fifth Annual ACM-SIAM Sympos. Discrete Algorithms (SODA) (SIAM, Philadelphia), 1433–1452.Google Scholar
• [6] 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
• [7] Chakrabarti A, Kale S (2015) Submodular maximization meets streaming: Matchings, matroids, and more. Math. Programming 154(1–2):225–247.Crossref, Google Scholar
• [8] Chan T-HH, Huang Z, Jiang SH-C, Kang N, Tang ZG (2018) Online submodular maximization with free disposal. ACM Trans. Algorithms 14(4):56.Crossref, Google Scholar
• [9] Chekuri C, Gupta S, Quanrud K (2015) Streaming algorithms for submodular function maximization. Halldórsson MM, Iwama K, Kobayashi N, Speckmann B, eds. Automata, Languages, and Programming (Springer, Berlin, Heidelberg), 318–330.Crossref, Google Scholar
• [10] Chekuri C, Jayram TS, Vondrák J (2015) On multiplicative weight updates for concave and submodular function maximization. Roughgarden T, ed. Proc. 2015 Conf. Innovations Theoret. Comput. Sci. (ITCS) (ACM, New York), 201.Google Scholar
• [11] 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
• [12] Ene A, Nguyen HL (2016) Constrained submodular maximization: Beyond 1/e. IEEE 57th Annual Sympos. Foundations Comput. Sci. (FOCS) (IEEE, Piscataway, NJ), 248–257.Google Scholar
• [13] Feige U (1998) A threshold of lnn for approximating set cover. J. ACM 45(4):634–652.Crossref, Google Scholar
• [14] Feige U, Mirrokni VS, Vondrák J (2011) Maximizing non-monotone submodular functions. SIAM J. Comput. 40(4):1133–1153.Crossref, Google Scholar
• [15] Feldman M, Naor J, Schwartz R (2011) A unified continuous greedy algorithm for submodular maximization. IEEE 52nd Annual Sympos. Foundations Comput. Sci. (FOCS) (IEEE, Piscataway, NJ), 570–579.Google Scholar
• [16] Feldman M, Norouzi-Fard A, Svensson O, Zenklusen R (2023) The one-way communication complexity of submodular maximization with applications to streaming and robustness. J. ACM 70(4):24.Crossref, Google Scholar
• [17] Filmus Y, Ward J (2014) Monotone submodular maximization over a matroid via non-oblivious local search. SIAM J. Comput. 43(2):514–542.Crossref, Google Scholar
• [18] Gharan SO, Vondrák J (2011) Submodular maximization by simulated annealing. Proc. Twenty-Second Annual ACM-SIAM Sympos. Discrete Algorithms (SODA), 1098–1116.Google Scholar
• [19] Haba R, Kazemi E, Feldman M, Karbasi A (2020) Streaming submodular maximization under a k-set system constraint. Proc. 37th Internat. Conf. Machine Learn. (ICML) (SIAM, Philadelphia), 3939–3949.Google Scholar
• [20] Harshaw C, Kazemi E, Feldman M, Karbasi A (2022) The power of subsampling in submodular maximization. Math. Oper. Res. 47(2):1365–1393.Link, Google Scholar
• [21] Huang C, Kakimura N (2022) Multi-pass streaming algorithms for monotone submodular function maximization. Theory Comput. Systems 66(1):354–394.Crossref, Google Scholar
• [22] Huang C, Thiery T, Ward J (2020) Improved multi-pass streaming algorithms for submodular maximization with matroid constraints. Byrka J, Meka R, eds. Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM), vol. 176 (Schloss Dagstuhl—Leibniz-Zentrum für Informatik, Wadern, Germany), 62:1–62:19.Google Scholar
• [23] Krause A (2013) Submodularity in machine learning. Accessed January 1, 2025, http://submodularity.org/.Google Scholar
• [24] 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 2009 (ACM, New York), 323–332.Google Scholar
• [25] Liu P, Rubinstein A, Vondrák J, Zhao J (2021) Cardinality constrained submodular maximization for random streams. Preprint, submitted November 14, https://arxiv.org/abs/2111.07217.Google Scholar
• [26] McGregor A, Vu HT (2019) Better streaming algorithms for the maximum coverage problem. Theory Comput. Systems 63(7):1595–1619.Crossref, Google Scholar
• [27] Mirzasoleiman B, Badanidiyuru A, Karbasi A (2016) Fast constrained submodular maximization: Personalized data summarization. Proc. 33nd Internat. Conf. Machine Learn. (PMLR, New York), 1358–1367.Google Scholar
• [28] Mirzasoleiman B, Jegelka S, Krause A (2018) Streaming non-monotone submodular maximization: Personalized video summarization on the fly. Proc. Thirty-Second AAAI Conf. Artificial Intelligence (AAAI-18) (AAAI Press, Palo Alto, CA), 1379–1386.Google Scholar
• [29] 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
• [30] 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
• [31] 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, New York), 3826–3835.Google Scholar
• [32] Schrijver A (2003) Combinatorial Optimization: Polyhedra and Efficiency (Springer-Verlag, Berlin).Google Scholar
• [33] Shadravan M (2020) Improved submodular secretary problem with shortlists. Preprint, submitted October 2, https://arxiv.org/abs/2010.01901.Google Scholar
• [34] Shadravan M (2020) Submodular matroid secretary problem with shortlists. Preprint, submitted January 3, http://arxiv.org/abs/2001.00894.Google Scholar
• [35] Varadaraja AB (2011) Buyback problem—Approximate matroid intersection with cancellation costs. Internat. Colloquium Automata Languages Programming (ICALP) (Springer, Berlin, Heidelberg), 379–390.Google Scholar
• [36] Vondrák J (2013) Symmetry and approximability of submodular maximization problems. SIAM J. Comput. 42(1):265–304.Crossref, Google Scholar