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

✍ Scribed by Thomas Andreae

• Publisher: John Wiley and Sons
• Year: 2001
• Tongue: English
• Weight: 172 KB
• Volume: 38
• Category: Article
• ISSN: 0028-3045
• DOI: 10.1002/net.1024

✦ Synopsis

Abstract

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}} {\le} ({{3}\over{2}}\tau^{2} + {{1}\over{2}}{\tau}){c}_{{min}}$. In the present paper, by means of appropriately refining the T^3^‐algorithm, an improved performance guarantee of factor τ^2^ + τ (instead of ${{3}\over{2}}\tau^{2} + {{1}\over{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. © 2001 John Wiley & Sons, Inc.