AI RESEARCH
Accelerated Relax-and-Round for Concave Coverage Problems
arXiv CS.LG
•
ArXi:2605.06900v1 Announce Type: cross We present an accelerated relax-and-round algorithm for concave coverage problems, which generalize the classic maximum coverage problem. Building on the relax-and-round framework of Barman [STACS 2021], we propose two significant improvements. First, we replace the linear programming (LP) relaxation step with a projected accelerated gradient method applied to a smooth surrogate objective to achieve a $\widetilde{O}(mn \varepsilon^{-1})$ running time.