Name
Abstract | ||
|---|---|---|
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 -epsilon$ approximation using $O(log(1/epsilon) / epsilon)$ 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. |
Year | Venue | DocType |
|---|---|---|
2018 | arXiv: Data Structures and Algorithms | Journal |
Volume | Citations | PageRank |
abs/1812.01591 | 1 | 0.36 |
References | Authors | |
0 | 3 | |
Name | Order | Citations | PageRank |
|---|---|---|---|
| Alina Ene | 1 | 409 | 25.47 |
| Huy L. Nguyen | 2 | 376 | 32.33 |
| Adrian Vladu | 3 | 388 | 13.29 |