Performance guarantees for the TSP with a parameterized triangle inequality

Michael A. Bender, Chandra Chekuri

Research output: Chapter in Book/Report/Conference proceedingConference contribution

Abstract

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 it is NP-hard to obtain a (1 + ∈τ) approximation. Our upper bound improves upon the earlier known ratio of (3τ 2/2/+τ/2)[1] for all values of τ > 7/3.

Original languageEnglish (US)
Title of host publicationAlgorithms and Data Structures - 6th International Workshop, WADS 1999, Proceedings
EditorsFrank Dehne, Jorg-Rudiger Sack, Arvind Gupta, Roberto Tamassia
PublisherSpringer-Verlag Berlin Heidelberg
Pages80-85
Number of pages6
ISBN (Print)3540662790, 9783540662792
StatePublished - Jan 1 1999
Externally publishedYes
Event6th International Workshop on Algorithms and Data Structures, WADS 1999 - Vancouver, Canada
Duration: Aug 11 1999Aug 14 1999

Publication series

NameLecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)
Volume1663
ISSN (Print)0302-9743
ISSN (Electronic)1611-3349

Other

Other6th International Workshop on Algorithms and Data Structures, WADS 1999
CountryCanada
CityVancouver
Period8/11/998/14/99

ASJC Scopus subject areas

  • Theoretical Computer Science
  • Computer Science(all)

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

  • Cite this

    Bender, M. A., & Chekuri, C. (1999). Performance guarantees for the TSP with a parameterized triangle inequality. In F. Dehne, J-R. Sack, A. Gupta, & R. Tamassia (Eds.), Algorithms and Data Structures - 6th International Workshop, WADS 1999, Proceedings (pp. 80-85). (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics); Vol. 1663). Springer-Verlag Berlin Heidelberg.