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 τ ≥ 1, the distances satisfy the inequality dist (x, y) ≤ τ · (dist(x, z) + dist (z, y)) for every triple of vertices x, y, and z. We obtain a 4τ approximation and also show that for some ε₀ < 0 it is NP-hard to obtain a (1 + ε₀τ)-approximation for all τ ≥ 1. Our upper bound improves upon the earlier known ratio of (τ² + τ) for all values of τ > 3.