Polynomial-time approximation scheme for weighted planar graph TSP

Sanjeev Arora, Michelangelo Grigni, David Karger, Philip Klein, Andrzej Woloszyn

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

81 Scopus citations

Abstract

Given a planar graph on n nodes with costs (weights) on its edges, define the distance between nodes i and j as the length of the shortest path between i and j. Consider this as an instance of metric TSP. For any ε>0, our algorithm finds a salesman tour of total cost at most (1+ε) times optimal in time nO(1/ε(2)). We also present a quasi-polynomial time algorithm for the Steiner version of this problem.

Original languageEnglish (US)
Title of host publicationProceedings of the Annual ACM-SIAM Symposium on Discrete Algorithms
Editors Anon
PublisherSIAM
Pages33-41
Number of pages9
StatePublished - Dec 1 1998
EventProceedings of the 1998 9th Annual ACM SIAM Symposium on Discrete Algorithms - San Francisco, CA, USA
Duration: Jan 25 1998Jan 27 1998

Other

OtherProceedings of the 1998 9th Annual ACM SIAM Symposium on Discrete Algorithms
CitySan Francisco, CA, USA
Period1/25/981/27/98

All Science Journal Classification (ASJC) codes

  • Chemical Health and Safety
  • Software
  • Safety, Risk, Reliability and Quality
  • Discrete Mathematics and Combinatorics

Fingerprint Dive into the research topics of 'Polynomial-time approximation scheme for weighted planar graph TSP'. Together they form a unique fingerprint.

Cite this