Improved Approximation Ratios for Traveling Salesperson Tours and Paths in Directed Graphs
Improved Approximation Ratios for Traveling Salesperson Tours and Paths in Directed Graphs
复制标题
改进了有向图中旅行推销员游览和路径的近似比
DOI：
--
复制
发表时间：
2007
期刊：
影响因子：
--
通讯作者：
Mohit Singh
中科院分区：
文献类型：
--
作者：
U. Feige;Mohit Singh
在度量非对称旅行商问题中，输入是一个完全有向图，其中边的权重满足三角不等式，并且需要找到访问所有顶点的最小权重行走。非对称旅行商问题（ATSP）中的行走要求是循环的。非对称旅行商路径问题（ATSPP）中，要求行走从顶点t开始，到顶点t结束。
我们将ATSP的逼近比从$frac{4}{3} log_3nsimeq 0.84log_2n $提高到$frac{2}{3} log_2n $。这种改进是基于Kaplan等人[JACM 05]的算法的修改，该算法实现了先前的最佳近似比。我们还显示了从ATSPP减少到ATSP，失去了一个因素，最多2 + iH 3？在近似比中，其中0可以被选择为任意小，并且对于每一个固定的i/2，约简的运行时间是多项式的。结合我们改进的近似比ATSP，这建立了一个近似比$（frac{4}{3} + log_2 n$的ATSPP，提高了以前的最佳比率4log eNi_2？2.76 log 2 nof Chekuri and Kazakhstan [Approx 2006].
In metric asymmetric traveling salesperson problems the input is a complete directed graph in which edge weights satisfy the triangle inequality, and one is required to find a minimum weight walk that visits all vertices. In the asymmetric traveling salesperson problem (ATSP) the walk is required to be cyclic. In asymmetric traveling salesperson path problem (ATSPP), the walk is required to start at vertex sand to end at vertex t.
We improve the approximation ratio for ATSP from $frac{4}{3}log_3 n simeq 0.84log_2 n$ to $frac{2}{3}log_2 n$. This improvement is based on a modification of the algorithm of Kaplan et al [JACM 05] that achieved the previous best approximation ratio. We also show a reduction from ATSPP to ATSP that loses a factor of at most 2 + i¾?in the approximation ratio, where i¾?> 0 can be chosen to be arbitrarily small, and the running time of the reduction is polynomial for every fixed i¾?. Combined with our improved approximation ratio for ATSP, this establishes an approximation ratio of $(frac{4}{3} + epsilon)log_2 n$ for ATSPP, improving over the previous best ratio of 4log e ni¾? 2.76log 2 nof Chekuri and Pal [Approx 2006].