A Parallel Double Greedy Algorithm for Submodular Maximization

12/04/2018
by   Alina Ene, et al.
0

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((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.

READ FULL TEXT

Please sign up or login with your details

Forgot password? Click here to reset