On the Metric s-t Path Traveling Salesman Problem
On the Metric s-t Path Traveling Salesman Problem
复制标题
关于度量 s-t 路径旅行商问题
DOI：
10.1137/14096712x
复制
发表时间：
2014
期刊：
影响因子：
--
通讯作者：
Zhihan Gao
中科院分区：
文献类型：
--
作者：
Zhihan Gao
我们研究公制$ s $ - $ t $路径旅行推销员问题（TSP）。 AN，Kleinberg和Shmoys [第44届ACM计算理论研讨会论文集，2012年，第875---886页]在长期存在的$ \ frac {5} {3} {3} $ - 近似因素上改善了一个算法，并提出了算法这实现了一个近似因素$ \ frac {1+ \ sqrt {5}}} {2} \ oft1.61803 $。后来，SEBO [第16届整数编程和组合优化会议的会议记录，2013年，第362---374页]将近似因子进一步提高到$ \ frac {8} {5} $。我们提供了一个简单，独立的分析，统一了这两个结果。我们的主要贡献是统一的校正向量。此外，我们比较了$ s $ - $ t $ PATH TSP的两个不同的线性编程（LP）放松两个LP都有相同的（分数）最佳值。此外，我们表明，两种有限公司的积分解决方案的最低成本在$ ...的一倍之内。
We study the metric $s$--$t$ path traveling salesman problem (TSP). An, Kleinberg, and Shmoys [Proceedings of the 44th ACM Symposium on Theory of Computing, 2012, pp. 875--886] improved on the long-standing $\frac{5}{3}$-approximation factor and presented an algorithm that achieves an approximation factor of $\frac{1+\sqrt{5}}{2}\approx1.61803$. Later, Sebo [Proceedings of the 16th Conference on Integer Programming and Combinatorial Optimization, 2013, pp. 362--374] further improved the approximation factor to $\frac{8}{5}$. We present a simple, self-contained analysis that unifies both results; our main contribution is a unified correction vector. Additionally, we compare two different linear programming (LP) relaxations of the $s$--$t$ path TSP, namely, the path version of the Held--Karp LP relaxation for the TSP and a weaker LP relaxation, and we show that both LPs have the same (fractional) optimal value. Also, we show that the minimum cost of integral solutions of the two LPs are within a factor of $...