改进松弛-取整算法，高效解决凹覆盖问题。
Accelerated Relax-and-Round for Concave Coverage Problems
- 用光滑代理目标替代线性规划，加速求解过程。
- 对对数奖励函数实现0.827的逼近比，理论更优。
- 适合需快速求解高维覆盖问题的研究者使用。
本文提出一种加速的松弛-取整算法，用于求解广义的最大覆盖问题。基于Barman等人的框架，我们引入两项关键改进：首先，以投影加速梯度法替代线性规划松弛，实现$ ilde{O}(mn \varepsilon^{-1})$的运行时间；其次，设计一种结合Carathéodory分解与随机交换舍入的专用舍入策略。理论证明在新奖励函数下可达到紧逼近比，例如对对数奖励函数$φ(x) = /log(1 + x)$可达0.827的逼近比。在合成及真实图数据上的最大多覆盖实验表明，本算法优于使用先进线性规划求解器的方法。
原文摘要 · Abstract (English)
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 $\widetilde{O}(mn \varepsilon^{-1})$ running time. Second, we use a specialized rounding scheme for the hypersimplex that combines the Carathéodory 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 $φ(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.
Thank you to arXiv for use of its open access interoperability. PaperDance 不是 arXiv 官方产品；中文卡片由大模型生成，请以原文为准。