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 s ubset {u, v} of X a nonnegative real number c(u, v), the cost of {u, v}. Fo r tau is an element of R, tau greater than or equal to 1, we say that the p air (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-eleme nt subset {u, v, w} of X. For fixed tau greater than or equal to 1, we deno te by Delta tauTSP the Traveling Salesman Problem (TSP) restricted to input s (X, c) satisfying the tau -inequality. In a paper of the present author a nd H.-J. Bandelt [SIAM J Discr Math 8 (1995), 1-16], a heuristic, called th e T-3-algorithm, was proposed for the TSP and it was shown that this heuris tic is an approximation algorithm for Delta tauTSP with performance guarant ee c(approx) less than or equal to (3/2 tau (2) + 1/2 tau )c(min). In the p resent paper, by means of appropriately refining the T-3-algorithm, an impr oved 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 versi ons 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 present ed here. (C) 2001 John Wiley & Sons, Inc.