This is the authors' abstract. We don't add key points for this paper.
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.
Answers are grounded in this paper and cite their sources.
No takes yet. Share an insight, caveat, or question.
Ene et al. (2018) studied this question.
Synapse has enriched 8 closely related papers on similar clinical questions. Consider them for comparative context: