A Parallel Double Greedy Algorithm for Submodular Maximization
This addresses the need for efficient parallel algorithms in optimization, though it is incremental as it adapts an existing sequential method to a parallel setting.
The paper tackles the problem of maximizing non-negative submodular functions in parallel, achieving a nearly-optimal 1/2 - ε approximation using O(log(1/ε) / ε) parallel rounds of function evaluations.
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.