### 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 language | English (US) |
---|---|

Title of host publication | Algorithms and Data Structures - 6th International Workshop, WADS 1999, Proceedings |

Editors | Frank Dehne, Jorg-Rudiger Sack, Arvind Gupta, Roberto Tamassia |

Publisher | Springer-Verlag Berlin Heidelberg |

Pages | 80-85 |

Number of pages | 6 |

ISBN (Print) | 3540662790, 9783540662792 |

State | Published - Jan 1 1999 |

Externally published | Yes |

Event | 6th International Workshop on Algorithms and Data Structures, WADS 1999 - Vancouver, Canada Duration: Aug 11 1999 → Aug 14 1999 |

### Publication series

Name | Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics) |
---|---|

Volume | 1663 |

ISSN (Print) | 0302-9743 |

ISSN (Electronic) | 1611-3349 |

### Other

Other | 6th International Workshop on Algorithms and Data Structures, WADS 1999 |
---|---|

Country | Canada |

City | Vancouver |

Period | 8/11/99 → 8/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.