On the traveling salesman problem restricted to inputs satisfying a relaxed triangle inequality

For a finite set X , let c be a mapping which assigns to every two‐element subset { u, v } of X a nonnegative real number c ( u, v ), the cost of { u, v }. For τ ∈ ℝ, τ ≥ 1, we say that the pair ( X, c ) satisfies the τ‐ inequality (“ relaxed triangle inequality ”) if c ( u, v ) ≤ τ( c ( u, w ) + c ( w, v )) for each three‐element subset { u, v, w } of X . For fixed τ ≥ 1, we denote by Δ τ TSP the Traveling Salesman Problem (TSP) restricted to inputs ( X, c ) satisfying the τ‐inequality. In a paper of the present author and H.‐J. Bandelt [SIAM J Discr Math 8 (1995), 1–16], a heuristic, called the T 3 ‐ algorithm , was proposed for the TSP and it was shown that this heuristic is an approximation algorithm for Δ τ TSP with performance guarantee c_approx ≤ (32τ² + 12τ)c_min . In the present paper, by means of appropriately refining the T 3 ‐algorithm, an improved performance guarantee of factor τ 2 + τ (instead of 32τ² + 12τ ) is established (which is best possible for certain refined versions of the T 3 ‐algorithm). This settles a conjecture of Andreae and Bandelt. Also, related results are derived and examples are given which shed light on the original (unrefined) T 3 ‐algorithm and the improved version presented here.