Approximation algorithms for the TSP with sharpened triangle inequality

The traveling salesman problem (TSP) is one of the hardest optimization problems in NPO because it does not admit any polynomial-time approximation algorithm (unless P = NP). On the other hand we have a polynomial-time approximation scheme (PTAS) for the Euclidean TSP and the 3/2-approximation algorithm of Christofides for TSP instances satisfying the triangle inequality, In this paper, we consider Delta(beta)-TSP, for 1/2 < beta < 1, as a subproblem of the TSP whose input instances satisfy the beta-sharpened triangle inequality cost({u, v}) less than or equal to beta(cost({u, x}) + cost({x, v})) for all vertices u, v, x. This problem is APX-complete for every beta > 1/2. The main contribution of this paper is the presentation of three different methods for the design of polynomial-time approximation algorithms for Delta(beta)-TSP with 1/2 < beta < 1, where the approximation ratio lies between 1 and 3/2, depending on beta. (C) 2000 Elsevier Science B.V. All rights reserved.