An improved approximation algorithm for the asymmetric TSP with strengthened triangle inequality

摘要

We consider the asymmetric traveling salesperson problem with γ-parameterized triangle inequality for γ ∈ [1/2, 1). That means, the edge weights fulfill w(u, v) ≤ γ · (w(u, x) + w(x, v)) for all nodes u, v, x. Chandran and Ram [L.S. Chandran, L.S. Ram, Approximations for ATSP with parametrized triangle inequality, in: Proc. 19th Int. Symp. on Theoret. Aspects of Comput. Sci. (STACS), in: Lecture Notes in Comput. Sci., vol. 2285, Springer, Berlin, 2002, pp. 227-237] gave the first constant factor approximation algorithm with polynomial running time for this problem. They achieve performance ratio γ/(1 - γ). We devise an approximation algorithm with performance ratio (1 + γ)/(2 - γ - γ~3), which is better for γ ∈ [0.5437, 1), that is, for the particularly interesting large values of γ.