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 some parameter tau greater than or equal to 1, the distances satisfy the inequality 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 + epsilon(0)tau)-approximation for all tau greater than or equal to 1. Our upper bound improves upon the earlier known ratio of (tau(2) + tau) [1] for all values of tau > 3. (C) 2000 Elsevier Science B.V. All rights reserved.