An accelerated relax-and-round algorithm for concave coverage problems achieves Õ(mn ε^{-1}) runtime and a 0.827-approximation ratio for the logarithmic reward function.
An exponential speedup in parallel running time for submodular maximization without loss in approximation
1 Pith paper cite this work. Polarity classification is still indexing.
1
Pith paper citing it
fields
cs.DS 1years
2026 1verdicts
UNVERDICTED 1representative citing papers
citing papers explorer
-
Accelerated Relax-and-Round for Concave Coverage Problems
An accelerated relax-and-round algorithm for concave coverage problems achieves Õ(mn ε^{-1}) runtime and a 0.827-approximation ratio for the logarithmic reward function.