An improved approximation algorithm for the ATSP with parameterized triangle inequality

作者：Zhang Tongquan^*; Li Weidong; Li Jianping

来源：Journal of Algorithms, 2009, 64(2-3): 74-78.

DOI：10.1016/j.jalgor.2008.10.002

• Traveling salesman problem
• Parameterized triangle inequality
• Approximation algorithm

In this paper. we consider the asymmetric traveling salesman problem with the gamma- parameterized triangle inequality for gamma is an element of |1/2, 1|. That means the edge weights in the given complete graph G = (V, E, omega) satisfy omega(u, w) <= gamma . (omega(u, v) omega(v, w)) for all distinct nodes u, v, w is an element of V. L.S. Chandran and L.S. Ram gave the first constant factor approximation algorithm with polynomial running time for this problem. They achieve performance ratio. gamma/1-gamma. M. Blaser, B. Manthey and J. Sgall obtain a 1 gamma/2-gamma-gamma(3)-approximation algorithm. We devise an approximation algorithm with performance ratio max{1 gamma(3)/1-gamma(2), gamma gamma(2) 1/2 gamma(3)/1(-)gamma(2)}, which is better than both 1 gamma/2-gamma-gamma(3) and gamma/1-gamma for almost all gamma is an element of |1/2, 1|.

• 出版日期2009-7
• 单位云南大学