An Optimal Approximation for Submodular Maximization Under a Matroid Constraint in the Adaptive Complexity Model

References

• Agarwal A, Agarwal S, Assadi S, Khanna S (2017) Learning with limited rounds of adaptivity: Coin tossing, multi-armed bandits, and ranking from pairwise comparisons. Proc. Conf. Learn. Theory (COLT), 39–75.Google Scholar
• Agrawal S, Shadravan M, Stein C (2018) Submodular secretary problem with shortlists. Preprint, submitted September 13, https://arxiv.org/abs/1809.05082.Google Scholar
• Badanidiyuru A, Vondrák J (2014) Fast algorithms for maximizing submodular functions. Proc. 25th Annual ACM-SIAM Symp. Discrete Algorithms (SIAM), 1497–1514.Google Scholar
• Badanidiyuru A, Mirzasoleiman B, Karbasi A, Krause A (2014) Streaming submodular maximization: Massive data summarization on the fly. Proc. 20th ACM SIGKDD Internat. Conf. Knowledge Discovery Data Mining, 671–680.Google Scholar
• Balkanski E, Singer Y (2017) The sample complexity of optimizing a convex function. Proc. Conf. Learn. Theory, 275–301.Google Scholar
• Balkanski E, Singer Y (2018a) The adaptive complexity of maximizing a submodular function. Proc. 50th Annual ACM SIGACT Symp. Theory Comput. (ACM), 1138–1151.Google Scholar
• Balkanski E, Singer Y (2018b) Approximation guarantees for adaptive sampling. Internat. Conf. Machine Learn., 393–402.Google Scholar
• Balkanski E, Breuer A, Singer Y (2018) Non-monotone submodular maximization in exponentially fewer iterations. NIPS’18 Proc. 32nd Internat. Conf. Neural Information Processing Systems 2018 (Curran Associates Inc., Red Hook, NY), 2359–2370.Google Scholar
• Balkanski E, Rubinstein A, Singer Y (2019) An exponential speedup in parallel running time for submodular maximization without loss in approximation. Proc. 2019 Annual ACM-SIAM Sympos. Discrete Algorithms (SODA) (Society for Industrial and Applied Mathematics, Philadelphia), 283–302.Google Scholar
• Barbosa R, Ene A, Nguyen H, Ward J (2015) The power of randomization: Distributed submodular maximization on massive datasets. Proc. Internat. Conf. Machine Learn. (ICML), 1236–1244.Google Scholar
• Barbosa RdP, Ene A, Nguyen HL, Ward J (2016) A new framework for distributed submodular maximization. Proc. Symp. Foundations Comput. Sci. (FOCS) (IEEE), 645–654.Google Scholar
• Berger B, Rompel J, Shor PW (1989) Efficient NC algorithms for set cover with applications to learning and geometry. Proc. Symp. Foundations Comput. Sci. (FOCS) (IEEE), 54–59.Google Scholar
• Blelloch GE (1996) Programming parallel algorithms. Comm. ACM 39(3):85–97.Crossref, Google Scholar
• Blelloch GE, Reid-Miller M (1998) Fast set operations using treaps. Proc. 10th Annual ACM Symp. Parallelism Algorithms Architectures (SPAA), 16–26.Google Scholar
• Blelloch GE, Peng R, Tangwongsan K (2011) Linear-work greedy parallel approximate set cover and variants. Proc. 23rd Annual ACM Symp. Parallelism Algorithms Architectures (SPAA), 23–32.Google Scholar
• Blelloch GE, Simhadri HV, Tangwongsan K (2012) Parallel and i/o efficient set covering algorithms. Proc. 24th Annual ACM Symp. Parallelism Algorithms Architectures (SPAA) (ACM), 82–90.Google Scholar
• Braverman M, Mao J, Weinberg SM (2016) Parallel algorithms for select and partition with noisy comparisons. Proc. 48th Annual ACM Symp. Theory Comput. (STOC), 851–862.Google Scholar
• Buchbinder N, Feldman M, Schwartz R (2014) Online submodular maximization with preemption. Proc. 26th Annual ACM-SIAM Symp. Discrete Algorithms (SIAM), 1202–1216.Google Scholar
• Buhrman H, García-Soriano D, Matsliah A, de Wolf R (2012) The non-adaptive query complexity of testing k-parities. Preprint, submitted September 18, https://arxiv.org/abs/1209.3849.Google Scholar
• Călinescu G, Chekuri C, Pál M, Vondrák J (2007) Maximizing a submodular set function subject to a matroid constraint (extended abstract). Proc. 12th Internat. Integer Programming Combin. Optim. Conf., 182–196.Google Scholar
• Canonne C, Gur T (2017) An adaptivity hierarchy theorem for property testing. Preprint, submitted February 19, https://arxiv.org/abs/1702.05678.Google Scholar
• Chakrabarti A, Kale S (2015) Submodular maximization meets streaming: Matchings, matroids, and more. Math. Programming 154(1–2):225–247.Crossref, Google Scholar
• Chekuri C, Quanrud K (2019a) Parallelizing greedy for submodular set function maximization in matroids and beyond. Proc. 51st Annual ACM SIGACT Symp. Theory Comput. (ACM), 78–89.Google Scholar
• Chekuri C, Quanrud K (2019b) Submodular function maximization in parallel via the multilinear relaxation. Proc. 2019 Annual ACM-SIAM Sympos. Discrete Algorithms (SODA) (Society for Industrial and Applied Mathematics, Philadelphia), 303–322.Google Scholar
• Chekuri C, Jayram T, Vondrák J (2015) On multiplicative weight updates for concave and submodular function maximization. Proc. Conf. Innovations Theoret. Comput. Sci. (ACM), 201–210.Google Scholar
• Chekuri C, Vondrák J, Zenklusen R (2009) Dependent randomized rounding for matroid polytopes and applications. Preprint, submitted September 24, https://arxiv.org/abs/0909.4348.Google Scholar
• Chen X, Servedio RA, Tan LY, Waingarten E, Xie J (2017) Settling the query complexity of non-adaptive junta testing. Preprint, submitted April 20, https://arxiv.org/abs/1704.06314.Google Scholar
• Cole R (1988) Parallel merge sort. SIAM J. Comput. 17(4):770–785.Crossref, Google Scholar
• Das A, Kempe D (2011) Submodular meets spectral: Greedy algorithms for subset selection, sparse approximation and dictionary selection. Preprint, submitted February 19, https://arxiv.org/abs/1102.3975.Google Scholar
• Duris P, Galil Z, Schnitger G (1984) Lower bounds on communication complexity. Proc. 16th Annual ACM Symp. Theory Comput. (STOC), 81–91.Google Scholar
• Ene A, Nguyen HL (2019) Submodular maximization with nearly-optimal approximation and adaptivity in nearly-linear time. Proc. 2019 Annual ACM-SIAM Sympos. Discrete Algorithms (SODA) (Society for Industrial and Applied Mathematics, Philadelphia), 274–282.Google Scholar
• Ene A, Nguyen HL, Vladu A (2019) Submodular maximization with matroid and packing constraints in parallel. Proc. 51st Annual ACM SIGACT Symp. Theory Comput. (ACM), 90–101.Google Scholar
• Epasto A, Mirrokni VS, Zadimoghaddam M (2017) Bicriteria distributed submodular maximization in a few rounds. Proc. 29th ACM Symp. Parallelism Algorithms Architectures (SPAA), 25–33.Google Scholar
• Fahrbach M, Mirrokni V, Zadimoghaddam M (2019a) Non-monotone submodular maximization with nearly optimal adaptivity complexity, 1833–1842.Google Scholar
• Fahrbach M, Mirrokni V, Zadimoghaddam M (2019b) Submodular maximization with optimal approximation, adaptivity and query complexity. Proc. 30th Annual ACM-SIAM Symp. Discrete Algorithms (SODA).Google Scholar
• Guestrin C, Krause A, Singh AP (2005) Near-optimal sensor placements in Gaussian processes. Proc. 22nd Internat. Conf. Machine Learn., 265–272.Google Scholar
• Haupt J, Nowak R, Castro R (2009a) Adaptive sensing for sparse signal recovery. Digital Signal Processing Workshop 5th IEEE Signal Processing Ed. Workshop (IEEE), 702–707.Google Scholar
• Haupt JD, Baraniuk RG, Castro RM, Nowak RD (2009b) Compressive distilled sensing: Sparse recovery using adaptivity in compressive measurements. Record 43rd Asilomar Conf. Signals Systems Comput. (IEEE), 1551–1555.Google Scholar
• Indyk P, Price E, Woodruff DP (2011) On the power of adaptivity in sparse recovery. Proc. Annual IEEE Symp. Foundations Comput. Sci. (FOCS) (IEEE), 285–294.Google Scholar
• Karp RM, Upfal E, Wigderson A (1988) The complexity of parallel search. J. Comput. System Sci. 36(2):225–253.Crossref, Google Scholar
• 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. Preprint, submitted May 2, https://arxiv.org/abs/1905.00948.Google Scholar
• Kempe D, Kleinberg J, Tardos É (2003) Maximizing the spread of influence through a social network. Proc. 9th ACM SIGKDD Internat. Conf. Knowledge Discovery Data Mining, 137–146.Google Scholar
• Kumar R, Moseley B, Vassilvitskii S, Vattani A (2015) Fast greedy algorithms in MapReduce and streaming. ACM Trans. Parallel Comput. 2(3):14.Crossref, Google Scholar
• Lin H, Bilmes J (2011) A class of submodular functions for document summarization. Proc. 49th Annual Meeting Assoc. Comput. Linguistics Human Language Tech., 510–520.Google Scholar
• Mirrokni V, Zadimoghaddam M (2015) Randomized composable core-sets for distributed submodular maximization. Proc. 47th Annual ACM Symp. Theory Comput. (STOC), 153–162.Google Scholar
• Mirzasoleiman B, Badanidiyuru A, Karbasi A (2016) Fast constrained submodular maximization: Personalized data summarization. Proc. 33rd Internat. Conf. Machine Learn. (ICML), 1358–1367.Google Scholar
• Mirzasoleiman B, Karbasi A, Badanidiyuru A, Krause A (2015) Distributed submodular cover: Succinctly summarizing massive data. Proc. 28th Internat. Conf. Neural Inform. Processing Systems (NIPS), 2881–2889.Google Scholar
• Mirzasoleiman B, Karbasi A, Sarkar R, Krause A (2013) Distributed submodular maximization: Identifying representative elements in massive data Proc. 26th Internat. Conf. Neural Inform. Processing Systems (NIPS), 2049–2057.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—i. Math. Programming 14(1):265–294.Crossref, Google Scholar
• Nisan N, Widgerson A (1991) Rounds in communication complexity revisited. Proc. 23rd annual ACM Symp. Theory Comput. (STOC), 419–429.Google Scholar
• Norouzi-Fard A, Tarnawski J, Mitrović S, Zandieh A, Mousavifar A, Svensson O (2018) Beyond 1/2-approximation for submodular maximization on massive data streams. Preprint, submitted August 6, https://export.arxiv.org/abs/1808.01842.Google Scholar
• Nutov Z, Shoham E (2020) Practical budgeted submodular maximization. Preprint, submitted July 9, https://arxiv.org/abs/2007.04937.Google Scholar
• Papadimitriou CH, Sipser M (1984) Communication complexity. J. Comput. System Sci. 28(2):260–269.Crossref, Google Scholar
• Rajagopalan S, Vazirani VV (1998) Primal-dual RNC approximation algorithms for set cover and covering integer programs. SIAM J. Comput. 28(2):525–540.Crossref, Google Scholar
• 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
• Valiant LG (1975) Parallelism in comparison problems. SIAM J. Comput. 4(3):348–355.Crossref, Google Scholar
• Vondrák J (2008) Optimal approximation for the submodular welfare problem in the value oracle model. Proc. 40th Annual ACM Symp. Theory Comput., 67–74.Google Scholar
• Vondrák J, Chekuri C, Zenklusen R (2011) Submodular function maximization via the multilinear relaxation and contention resolution schemes. Proc. 43rd Annual ACM Symp. Theory Comput. (ACM), 783–792.Google Scholar