OASIcs.SOSA.2019.18.pdf
- Filesize: 464 kB
- 10 pages
Document
Submodular Optimization in the MapReduce Model
Authors
-
Part of:
Volume:
2nd Symposium on Simplicity in Algorithms (SOSA 2019)
Series: Open Access Series in Informatics (OASIcs) - License:
Creative Commons Attribution 3.0 Unported license
- Publication Date: 2019-01-08
Cite As Get BibTex
Paul Liu and Jan Vondrak. Submodular Optimization in the MapReduce Model. In 2nd Symposium on Simplicity in Algorithms (SOSA 2019). Open Access Series in Informatics (OASIcs), Volume 69, pp. 18:1-18:10, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2019)
https://doi.org/10.4230/OASIcs.SOSA.2019.18
Abstract
Submodular optimization has received significant attention in both practice and theory, as a wide array of problems in machine learning, auction theory, and combinatorial optimization have submodular structure. In practice, these problems often involve large amounts of data, and must be solved in a distributed way. One popular framework for running such distributed algorithms is MapReduce. In this paper, we present two simple algorithms for cardinality constrained submodular optimization in the MapReduce model: the first is a (1/2-o(1))-approximation in 2 MapReduce rounds, and the second is a (1-1/e-epsilon)-approximation in (1+o(1))/epsilon MapReduce rounds.
Subject Classification
Keywords
- mapreduce
- submodular
- optimization
- approximation algorithms
Metrics
- Access Statistics
-
Total Accesses (updated on a weekly basis)
0PDF Downloads
References
-
Sepehr Assadi and Sanjeev Khanna. Randomized Composable Coresets for Matching and Vertex Cover. In ACM Symposium on Parallelism in Algorithms and Architectures (SPAA), 2017.
- Sepehr Assadi and Sanjeev Khanna. Tight Bounds on the Round Complexity of the Distributed Maximum Coverage Problem. In Proceedings of the Twenty-Ninth Annual ACM-SIAM Symposium on Discrete Algorithms, SODA 2018, New Orleans, LA, USA, January 7-10, 2018, pages 2412-2431, 2018. URL: http://dx.doi.org/10.1137/1.9781611975031.155.
- Eric Balkanski, Adam Breuer, and Yaron Singer. Non-monotone Submodular Maximization in Exponentially Fewer Iterations. CoRR, abs/1807.11462, 2018. URL: http://arxiv.org/abs/1807.11462.
- Eric Balkanski, Aviad Rubinstein, and Yaron Singer. An Exponential Speedup in Parallel Running Time for Submodular Maximization without Loss in Approximation. CoRR, abs/1804.06355, 2018. URL: http://arxiv.org/abs/1804.06355.
-
Rafael da Ponte Barbosa, Alina Ene, Huy L. Nguyen, and Justin Ward. A New Framework for Distributed Submodular Maximization. In Proceedings of the IEEE 57th Annual Symposium on Foundations of Computer Science, 2016.
-
Satoru Fujishige. Submodular functions and optimization, volume 58. Elsevier, 2005.
- Howard J. Karloff, Siddharth Suri, and Sergei Vassilvitskii. A Model of Computation for MapReduce. In Proceedings of the Twenty-First Annual ACM-SIAM Symposium on Discrete Algorithms (SODA), pages 938-948, 2010. URL: http://dx.doi.org/10.1137/1.9781611973075.76.
- Ravi Kumar, Benjamin Moseley, Sergei Vassilvitskii, and Andrea Vattani. Fast Greedy Algorithms in MapReduce and Streaming. TOPC, 2(3):14:1-14:22, 2015. URL: http://dx.doi.org/10.1145/2809814.
- Andrew McGregor and Hoa T. Vu. Better Streaming Algorithms for the Maximum Coverage Problem. In 20th International Conference on Database Theory, ICDT 2017, March 21-24, 2017, Venice, Italy, pages 22:1-22:18, 2017. URL: http://dx.doi.org/10.4230/LIPIcs.ICDT.2017.22.
-
Vahab S. Mirrokni and Morteza Zadimoghaddam. Randomized Composable Core-sets for Distributed Submodular Maximization. In ACM Symposium on Theory of Computing (STOC), pages 153-162, 2015.
- George L. Nemhauser, Laurence A. Wolsey, and Marshall L. Fisher. An analysis of approximations for maximizing submodular set functions - I. Math. Program., 14(1):265-294, 1978. URL: http://dx.doi.org/10.1007/BF01588971.
-
Martin Raab and Angelika Steger. "Balls into Bins" - A Simple and Tight Analysis. In Michael Luby, José D. P. Rolim, and Maria Serna, editors, Randomization and Approximation Techniques in Computer Science, pages 159-170, Berlin, Heidelberg, 1998. Springer Berlin Heidelberg.