2018/12/04 by Alina Ene, Ene, Alina, Huy L. Nguyên +3
Computer Science · #Complexity and Algorithms in Graphs #Cryptography and Data Security #Privacy-Preserving Technologies in Data
paper · pdf · doi:10.48550/arxiv.1812.01591
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.