# Distributed Submodular Maximization

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

## Key facts

- Cited by 20 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 3 Nov 2014.

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

- [Submodularity In Machine Learning and Artificial Intelligence](https://mlsanity.com/paper/2202.00132/) (2022)
- [Submodular + Concave](https://mlsanity.com/paper/2106.04769/) (2021)
- [Deletion Robust Submodular Maximization over Matroids](https://mlsanity.com/paper/2201.13128/) (2022)
- [Resource-Aware Distributed Submodular Maximization: A Paradigm for Multi-Robot Decision-Making](https://mlsanity.com/paper/2204.07520/) (2022)
- [Maximizing Submodular Functions for Recommendation in the Presence of Biases](https://mlsanity.com/paper/2305.02806/) (2023)
- [Sparsification of Decomposable Submodular Functions](https://mlsanity.com/paper/2201.07289/) (2022)
- [The Power of Subsampling in Submodular Maximization](https://mlsanity.com/paper/2104.02772/) (2021)
- [Balancing Utility and Fairness in Submodular Maximization (Technical Report)](https://mlsanity.com/paper/2211.00980/) (2022)
- [Learning on Bandwidth Constrained Multi-Source Data with MIMO-inspired DPP MAP Inference](https://mlsanity.com/paper/2306.02497/) (2023)
- [MUSS: Multilevel Subset Selection for Relevance and Diversity](https://mlsanity.com/paper/2503.11126/) (2025)
- [Max-Utility Based Arm Selection Strategy For Sequential Query Recommendations](https://mlsanity.com/paper/2108.13810/) (2021)
- [Practical Parallel Algorithms for Non-Monotone Submodular Maximization](https://mlsanity.com/paper/2308.10656/) (2023)
- [Mini-batch Submodular Maximization](https://mlsanity.com/paper/2401.12478/) (2024)
- [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)
- [Deep Submodular Peripteral Networks](https://mlsanity.com/paper/2403.08199/) (2024)
- [Scalable Projection-Free Optimization](https://mlsanity.com/paper/2105.03527/) (2021)
- [Revisiting Matching Pursuit: Beyond Approximate Submodularity](https://mlsanity.com/paper/2305.07782/) (2023)
- [Scalable Submodular Policy Optimization via Pruned Submodularity Graph](https://mlsanity.com/paper/2507.13834/) (2025)
- [UrbanHuRo: A Two-Layer Human-Robot Collaboration Framework for the Joint Optimization of Heterogeneous Urban Services](https://mlsanity.com/paper/2603.03701/) (2026)

## Abstract (arXiv)

Many large-scale machine learning problems--clustering, non-parametric learning, kernel machines, etc.--require selecting a small yet representative subset from a large dataset. Such problems can often be reduced to maximizing a submodular set function subject to various constraints. Classical approaches to submodular optimization require centralized access to the full dataset, which is impractical for truly large-scale problems. In this paper, we consider the problem of submodular function maximization in a distributed fashion. We develop a simple, two-stage protocol GreeDi, that is easily implemented using MapReduce style computations. We theoretically analyze our approach, and show that under certain natural conditions, performance close to the centralized approach can be achieved. We begin with monotone submodular maximization subject to a cardinality constraint, and then extend this approach to obtain approximation guarantees for (not necessarily monotone) submodular maximization subject to more general constraints including matroid or knapsack constraints. In our extensive experiments, we demonstrate the effectiveness of our approach on several applications, including sparse Gaussian process inference and exemplar based clustering on tens of millions of examples using Hadoop.