# A Parallel Double Greedy Algorithm for Submodular Maximization

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

## Key facts

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

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

- [Submodular Maximization subject to a Knapsack Constraint: Combinatorial Algorithms with Near-optimal Adaptive Complexity](https://mlsanity.com/paper/2102.08327/) (2021)

## Abstract (arXiv)

We study parallel algorithms for the problem of maximizing a non-negative submodular function. Our main result is an algorithm that achieves a nearly-optimal 1/2 -ε approximation using O(log(1/ε) / ε) parallel rounds of function evaluations. Our algorithm is based on a continuous variant of the double greedy algorithm of Buchbinder et al. that achieves the optimal 1/2 approximation in the sequential setting. Our algorithm applies more generally to the problem of maximizing a continuous diminishing-returns (DR) function.