# Accelerated Relax-and-Round for Concave Coverage Problems

arXiv: https://arxiv.org/abs/2605.06900 · HTML: https://mlsanity.com/paper/2605.06900/

## Key facts

- No citing papers in the map yet (data through 14 Oct 2026).
- Builds on 27 of its 47 references that are in the map.
- First posted on arXiv 7 May 2026.

## Builds on (most cited first, 27 of 27)

- [Convex optimization](https://mlsanity.com/paper/2106.01946/) (2021)
- [Selection via Proxy: Efficient Data Selection for Deep Learning](https://mlsanity.com/paper/1906.11829/) (2019)
- [Solving Linear Programs in the Current Matrix Multiplication Time](https://mlsanity.com/paper/1810.07896/) (2018)
- [How to Train Data-Efficient LLMs](https://mlsanity.com/paper/2402.09668/) (2024)
- [Parallelizing the dual revised simplex method](https://mlsanity.com/paper/1503.01889/) (2015)
- [Active Learning Through a Covering Lens](https://mlsanity.com/paper/2205.11320/) (2022)
- [A Deterministic Linear Program Solver in Current Matrix Multiplication Time](https://mlsanity.com/paper/1910.11957/) (2019)
- [Submodularity In Machine Learning and Artificial Intelligence](https://mlsanity.com/paper/2202.00132/) (2022)
- [More Asymmetry Yields Faster Matrix Multiplication](https://mlsanity.com/paper/2404.16349/) (2024)
- [Randomized Composable Core-sets for Distributed Submodular Maximization](https://mlsanity.com/paper/1506.06715/) (2015)
- [SMART: Submodular Data Mixture Strategy for Instruction Tuning](https://mlsanity.com/paper/2403.08370/) (2024)
- [Projection onto the capped simplex](https://mlsanity.com/paper/1503.01002/) (2015)
- [Submodular Maximization with Nearly Optimal Approximation, Adaptivity and Query Complexity](https://mlsanity.com/paper/1807.07889/) (2018)
- [The Power of Randomization: Distributed Submodular Maximization on Massive Datasets](https://mlsanity.com/paper/1502.02606/) (2015)
- [An Exponential Speedup in Parallel Running Time for Submodular Maximization without Loss in Approximation](https://mlsanity.com/paper/1804.06355/) (2018)
- [Stochastic Submodular Maximization: The Case of Coverage Functions](https://mlsanity.com/paper/1711.01566/) (2017)
- [MixMin: Finding Data Mixtures via Convex Minimization](https://mlsanity.com/paper/2502.10510/) (2025)
- [Submodular Maximization with Nearly-optimal Approximation and Adaptivity in Nearly-linear Time](https://mlsanity.com/paper/1804.05379/) (2018)
- [Submodular Optimization in the MapReduce Model](https://mlsanity.com/paper/1810.01489/) (2018)
- [Tight Approximation Bounds for Maximum Multi-Coverage](https://mlsanity.com/paper/1905.00640/) (2019)
- [Tight Approximation Guarantees for Concave Coverage Problems](https://mlsanity.com/paper/2010.00970/) (2020)
- [Geometric Algorithms for Neural Combinatorial Optimization with Constraints](https://mlsanity.com/paper/2510.24039/) (2025)
- [The SCIP Optimization Suite 10.0](https://mlsanity.com/paper/2511.18580/) (2025)
- [Fast Projection onto the Capped Simplex with Applications to Sparse Regression in Bioinformatics](https://mlsanity.com/paper/2110.08471/) (2021)
- [Scalable Distributed Algorithms for Size-Constrained Submodular Maximization in the MapReduce and Adaptive Complexity Models](https://mlsanity.com/paper/2206.09563/) (2022)
- [GIST: Greedy Independent Set Thresholding for Max-Min Diversification with Submodular Utility](https://mlsanity.com/paper/2405.18754/) (2024)
- [Procurement Auctions via Approximately Optimal Submodular Optimization](https://mlsanity.com/paper/2411.13513/) (2024)

## Abstract (arXiv)

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 et al. [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 widetildeO(mn varepsilon-1) running time. Second, we use a specialized rounding scheme for the hypersimplex that combines the Carath'eodory decomposition algorithm in Karalias et al. [NeurIPS 2025] with randomized swap rounding of Chekuri et al. [FOCS 2010]. We prove tight approximation ratios for new reward functions, including a 0.827-approximation for the logarithmic reward varphi(x) = log(1 + x). Finally, we conduct maximum multi-coverage experiments on synthetic and real-world graphs, demonstrating that our algorithm outperforms approaches that use state-of-the-art LP solvers.