查看“WikiEdge:ArXiv速递/2025-04-15”的源代码

== 摘要 ==
* '''原文标题'''：Breaking a Long-Standing Barrier: 2-$\varepsilon$ Approximation for Steiner Forest
* '''中文标题'''：突破长期障碍：斯坦纳森林问题的2-ε近似算法
* '''发布日期'''：2025-04-15 17:13:48+00:00
* '''作者'''：Ali Ahmadi, Iman Gholami, MohammadTaghi Hajiaghayi, Peyman Jabbarzade, Mohammad Mahdavi
* '''分类'''：cs.DS
*'''原文链接'''：http://arxiv.org/abs/2504.11398v1
'''中文摘要'''：[[斯坦纳森林问题]]（又称广义[[斯坦纳树问题]]）是边加权图上的一个基本优化问题，其目标是在给定顶点对集合的情况下，选择一个最小成本的子图使得每对顶点都连通。该问题推广了1811年首次提出的[[斯坦纳树问题]]，后者的最佳已知近似因子为1.39 [[Byrka等，2010]]（[[STOC]] 2010最佳论文奖）。[[Agrawal等，1989]]（[[STOC]] 2023三十年时间检验奖）的开创性工作与[[Goemans和Williamson，1992]]（[[SICOMP]]'95）的改进，在35年前就建立了[[斯坦纳森林问题]]的2-近似算法。[[Jain]]（[[FOCS]]'98）开创性的迭代舍入技术后来将这些结果扩展到更高连通性场景。尽管该问题具有长期重要性，但突破2的近似因子始终是重大挑战，甚至引发类似[[顶点覆盖问题]]的猜想——获得更好因子可能确实困难。值得注意的是，包括[[Gupta和Kumar]]（[[STOC]]'15）以及[[Gro{\ss}等]]（[[ITCS]]'18）的基础性工作，分别提出了96和69近似算法，可能寄望为[[斯坦纳森林问题]]实现低于2的常数因子近似突破铺路。
本文通过设计一种新颖的确定性算法，实现了$2 - 10^{-11}$的近似比，突破了2的近似壁垒。作为方法的核心组件，我们还针对[[斯坦纳树问题]]提出了一种基于对偶的局部搜索算法，其近似保证为$1.943$，该成果本身也具有独立价值。