A better differential approximation ratio for symmetric TSP
In this paper, we study the approximability properties of symmetric TSP under an approximation measure called the differential ratio. More precisely, we improve up to 3/4 - epsilon (for any epsilon > 0) the best differential ratio of 2/3 known so far, given in Hassin and Khuller, [R. Hassin, S. Khuller, z-approximations, J. Algorithms, 41 (2) (2001) 429-442]. (C) 2008 Elsevier B.V. All rights reserved.
differential ratio approximation algorithm traveling salesman problem