Performance guarantees for the TSP with a parameterized triangle inequality

Michael A. Bender, Chandra Chekuri

Research output: Contribution to journalArticlepeer-review


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.

Original languageEnglish (US)
Pages (from-to)17-21
Number of pages5
JournalInformation Processing Letters
Issue number1-2
StatePublished - Jan 31 2000
Externally publishedYes

ASJC Scopus subject areas

  • Theoretical Computer Science
  • Signal Processing
  • Information Systems
  • Computer Science Applications


Dive into the research topics of 'Performance guarantees for the TSP with a parameterized triangle inequality'. Together they form a unique fingerprint.

Cite this