# Parallelizing greedy for submodular set function maximization in matroids and beyond

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

## Key facts

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

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

- [Batched Dueling Bandits](https://mlsanity.com/paper/2202.10660/) (2022)
- [Submodular Maximization subject to a Knapsack Constraint: Combinatorial Algorithms with Near-optimal Adaptive Complexity](https://mlsanity.com/paper/2102.08327/) (2021)
- [On the Complexity of Dynamic Submodular Maximization](https://mlsanity.com/paper/2111.03198/) (2021)
- [Fast Feature Selection with Fairness Constraints](https://mlsanity.com/paper/2202.13718/) (2022)
- [Adaptive Sampling for Fast Constrained Maximization of Submodular Function](https://mlsanity.com/paper/2102.06486/) (2021)
- [An Asymptotically Optimal Batched Algorithm for the Dueling Bandit Problem](https://mlsanity.com/paper/2209.12108/) (2022)
- [Practical Parallel Algorithms for Non-Monotone Submodular Maximization](https://mlsanity.com/paper/2308.10656/) (2023)
- [Sample-Adaptivity Tradeoff in On-Demand Sampling](https://mlsanity.com/paper/2511.15507/) (2025)
- [Oracle-Efficient Combinatorial Semi-Bandits](https://mlsanity.com/paper/2510.21431/) (2025)

## Abstract (arXiv)

We consider parallel, or low adaptivity, algorithms for submodular function maximization. This line of work was recently initiated by Balkanski and Singer and has already led to several interesting results on the cardinality constraint and explicit packing constraints. An important open problem is the classical setting of matroid constraint, which has been instrumental for developments in submodular function maximization. In this paper we develop a general strategy to parallelize the well-studied greedy algorithm and use it to obtain a randomized left(frac12 - εright)-approximation in operatornameOleft( fraclog2 nε2 right) rounds of adaptivity. We rely on this algorithm, and an elegant amplification approach due to Badanidiyuru and Vondr'ak to obtain a fractional solution that yields a near-optimal randomized left( 1 - 1/e - ε right)-approximation in Oleft( fraclog2 nε3 right)  rounds of adaptivity. For non-negative functions we obtain a left( 3-2√2right)-approximation and a fractional solution that yields a left( frac1e - εright)-approximation. Our approach for parallelizing greedy yields approximations for intersections of matroids and matchoids, and the approximation ratios are comparable to those known for sequential greedy.