Performance guarantees for the TSP with a parameterized triangle inequality

We consider the approximability of the TSP problem in graphs that satisfy a relaxed form of triangle inequality. More precisely, we assume that for so me parameter tau greater than or equal to 1, the distances satisfy the ineq uality dist(x, y) less than or equal to tau . (dist(x, z) + dist(z, y)) for every triple of vertices x, y, and z. We obtain a 4 tau-approximation and also show that for some epsilon(0) > 0 it is NP-hard to obtain a (1 + epsil on(0)tau)-approximation for all tau greater than or equal to 1. Our upper b ound improves upon the earlier known ratio of (tau(2) + tau) [1] for all va lues of tau > 3. (C) 2000 Elsevier Science B.V. All rights reserved.