# Submodular Optimization in the MapReduce Model

arXiv: https://arxiv.org/abs/1810.01489 · HTML: https://mlsanity.com/paper/1810.01489/

## Key facts

- Cited by 8 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 2 Oct 2018.

## Built on by (most cited first, 8 of 8)

- [Instance Specific Approximations for Submodular Maximization](https://mlsanity.com/paper/2102.11911/) (2021)
- [Scalable Distributed Algorithms for Size-Constrained Submodular Maximization in the MapReduce and Adaptive Complexity Models](https://mlsanity.com/paper/2206.09563/) (2022)
- [Dynamic Non-monotone Submodular Maximization](https://mlsanity.com/paper/2311.03685/) (2023)
- [On Distributed Larger-Than-Memory Subset Selection With Pairwise Submodular Functions](https://mlsanity.com/paper/2402.16442/) (2024)
- [GIST: Greedy Independent Set Thresholding for Max-Min Diversification with Submodular Utility](https://mlsanity.com/paper/2405.18754/) (2024)
- [Optimal Data Selection: An Online Distributed View](https://mlsanity.com/paper/2201.10547/) (2022)
- [A Dynamic Algorithm for Weighted Submodular Cover Problem](https://mlsanity.com/paper/2407.10003/) (2024)
- [Accelerated Relax-and-Round for Concave Coverage Problems](https://mlsanity.com/paper/2605.06900/) (2026)

## Abstract (arXiv)

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-ε)-approximation in frac1+o(1)ε MapReduce rounds.