Abstarct
We consider the asymmetric traveling salesperson problem with γ -parameterized triangle inequality for γ ∈ [1/2, 1). That means, the edge weights fulfill 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 which is better for γ ∈ [0.5437, 1), that is, for the particularly interesting large values of γ