TY - JOUR
T1 - Performance guarantees for the TSP with a parameterized triangle inequality
AU - Bender, Michael A.
AU - Chekuri, Chandra
N1 - Funding Information:
∗Corresponding author. Email: [email protected]. 1 Email: [email protected]. Supported in part by ISX Corporation and Hughes Research Laboratories.
PY - 2000/1/31
Y1 - 2000/1/31
N2 - We consider the approximability of the TSP problem in graphs that satisfy a relaxed form of triangle inequality. More precisely, we assume that for some parameter τ ≥ 1, the distances satisfy the inequality dist (x, y) ≤ τ · (dist(x, z) + dist (z, y)) for every triple of vertices x, y, and z. We obtain a 4τ approximation and also show that for some ε0 < 0 it is NP-hard to obtain a (1 + ε0τ)-approximation for all τ ≥ 1. Our upper bound improves upon the earlier known ratio of (τ2 + τ) for all values of τ > 3.
AB - We consider the approximability of the TSP problem in graphs that satisfy a relaxed form of triangle inequality. More precisely, we assume that for some parameter τ ≥ 1, the distances satisfy the inequality dist (x, y) ≤ τ · (dist(x, z) + dist (z, y)) for every triple of vertices x, y, and z. We obtain a 4τ approximation and also show that for some ε0 < 0 it is NP-hard to obtain a (1 + ε0τ)-approximation for all τ ≥ 1. Our upper bound improves upon the earlier known ratio of (τ2 + τ) for all values of τ > 3.
UR - http://www.scopus.com/inward/record.url?scp=0033908689&partnerID=8YFLogxK
UR - http://www.scopus.com/inward/citedby.url?scp=0033908689&partnerID=8YFLogxK
U2 - 10.1016/S0020-0190(99)00160-X
DO - 10.1016/S0020-0190(99)00160-X
M3 - Article
AN - SCOPUS:0033908689
SN - 0020-0190
VL - 73
SP - 17
EP - 21
JO - Information Processing Letters
JF - Information Processing Letters
IS - 1-2
ER -