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
Pages80-85
Number of pages6
ISBN (Print)3540662790, 9783540662792
DOIs
StatePublished - 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