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, a heuristic, called the T3-algorithm, was proposed for the TSP and it was shown that this heuristic is an approximation algorithm for Δτ TSP with performance guarantee capprox≤(3/2τ2+1/2τ)cmin. In the present paper, by means of appropriately refining the T3-algorithm, an improved performance guarantee of factor τ2 + τ (instead of (3/2τ2+1/2τ) is established (which is best possible for certain refined versions of the T3-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) T3-algorithm and the improved version presented here.
