A 1.5-Approximation for Path TSP
A 1.5-Approximation for Path TSP
复制标题
DOI：
10.1137/1.9781611975482.93
复制
发表时间：
2018-05
期刊：
影响因子：
--
通讯作者：
R. Zenklusen
中科院分区：
文献类型：
--
作者：
R. Zenklusen
我们提出了一个$1.5$-近似度量路径旅行商问题（路径TSP）。最近对路径TSP的所有改进都关键地利用了An，Kleinberg和Shmoys [Journal of the ACM，2015]所示的结构属性，即相对于Held-Karp解决方案的窄切割形成链。我们显着偏离这些方法，通过显示处理更大的$s$-$t$削减的好处，即使他们是少得多的结构。更确切地说，我们证明了Traub和Vygen最近引入的动态规划思想的变体[SODA，2018]通过利用Karger关于近最小切割数量的开创性结果，足以处理更大尺寸的切割。这避免了Traub和Vygen使用的动态规划的递归应用，并导致一个相当简单的算法，避免了近似保证中的额外误差项。我们匹配仍然不败的1.5 $-近似保证Christofides的算法TSP。因此，路径TSP的逼近性的任何进一步的进展也将导致TSP的改进。
We present a $1.5$-approximation for the Metric Path Traveling Salesman Problem (Path TSP). All recent improvements on Path TSP crucially exploit a structural property shown by An, Kleinberg, and Shmoys [Journal of the ACM, 2015], namely that narrow cuts with respect to a Held-Karp solution form a chain. We significantly deviate from these approaches by showing the benefit of dealing with larger $s$-$t$ cuts, even though they are much less structured. More precisely, we show that a variation of the dynamic programming idea recently introduced by Traub and Vygen [SODA, 2018] is versatile enough to deal with larger size cuts, by exploiting a seminal result of Karger on the number of near-minimum cuts. This avoids a recursive application of dynamic programming as used by Traub and Vygen, and leads to a considerably simpler algorithm avoiding an additional error term in the approximation guarantee. We match the still unbeaten $1.5$-approximation guarantee of Christofides' algorithm for TSP. Hence, any further progress on the approximability of Path TSP will also lead to an improvement for TSP.