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 tau is an element of R, tau greater than or equal to 1, we say that the pair (X, c) satisfies the tau -inequality ("relaxed triangle inequality") if c(u, v) less than or equal to tau (c(u, w) + c(w, v)) for each three-element subset {u, v, w} of X. For fixed tau greater than or equal to 1, we denote by Delta tauTSP the Traveling Salesman Problem (TSP) restricted to inputs (X, c) satisfying the tau -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 Delta tauTSP with performance guarantee c(approx) less than or equal to (3/2 tau (2) + 1/2 tau )c(min). In the present paper, by means of appropriately refining the T-3-algorithm, an improved performance guarantee of factor tau (2) + tau (instead of 3/2 tau (2) + 1/2 tau) 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. (C) 2001 John Wiley & Sons, Inc.