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)γ∈[1/2,1). That means, the edge weights fulfill w(u,v)⩽γ⋅(w(u,x)+w(x,v))w(u,v)⩽γ⋅(w(u,x)+w(x,v)) for all nodes u,v,xu,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−γ)γ/(1−γ). We devise an approximation algorithm with performance ratio (1+γ)/(2−γ−γ3)(1+γ)/(2−γ−γ3), which is better for γ∈[0.5437,1)γ∈[0.5437,1), that is, for the particularly interesting large values of γ.