# The Power of Randomization: Distributed Submodular Maximization on Massive Datasets

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

## Key facts

- Cited by 13 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 9 Feb 2015.

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

- [Federated Combinatorial Multi-Agent Multi-Armed Bandits](https://mlsanity.com/paper/2405.05950/) (2024)
- [On the Complexity of Dynamic Submodular Maximization](https://mlsanity.com/paper/2111.03198/) (2021)
- [Best of Both Worlds: Practical and Theoretically Optimal Submodular Maximization in Parallel](https://mlsanity.com/paper/2111.07917/) (2021)
- [MUSS: Multilevel Subset Selection for Relevance and Diversity](https://mlsanity.com/paper/2503.11126/) (2025)
- [Scalable Distributed Algorithms for Size-Constrained Submodular Maximization in the MapReduce and Adaptive Complexity Models](https://mlsanity.com/paper/2206.09563/) (2022)
- [Practical Parallel Algorithms for Non-Monotone Submodular Maximization](https://mlsanity.com/paper/2308.10656/) (2023)
- [Decomposable Submodular Maximization in Federated Setting](https://mlsanity.com/paper/2402.00138/) (2024)
- [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)
- [Composable Coresets for Determinant Maximization: Greedy is Almost Optimal](https://mlsanity.com/paper/2309.15286/) (2023)
- [GreedyML: A Parallel Algorithm for Maximizing Constrained Submodular Functions](https://mlsanity.com/paper/2403.10332/) (2024)
- [Accelerated Relax-and-Round for Concave Coverage Problems](https://mlsanity.com/paper/2605.06900/) (2026)

## Abstract (arXiv)

A wide variety of problems in machine learning, including exemplar clustering, document summarization, and sensor placement, can be cast as constrained submodular maximization problems. Unfortunately, the resulting submodular optimization problems are often too large to be solved on a single machine. We develop a simple distributed algorithm that is embarrassingly parallel and it achieves provable, constant factor, worst-case approximation guarantees. In our experiments, we demonstrate its efficiency in large problems with different kinds of constraints with objective values always close to what is achievable in the centralized setting.