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: chekuri@research.bell-labs.com. 1 Email: bender@cs.sunysb.edu. 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 -