Polynomial-time approximation scheme for weighted planar graph TSP

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

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 proceeding › Conference contribution

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 n^O(1/ε(2)). We also present a quasi-polynomial time algorithm for the Steiner version of this problem.

Original language	English (US)
Title of host publication	Proceedings of the Annual ACM-SIAM Symposium on Discrete Algorithms
Editors	Anon
Publisher	SIAM
Pages	33-41
Number of pages	9
State	Published - Dec 1 1998
Event	Proceedings of the 1998 9th Annual ACM SIAM Symposium on Discrete Algorithms - San Francisco, CA, USA Duration: Jan 25 1998 → Jan 27 1998

Other

Other	Proceedings of the 1998 9th Annual ACM SIAM Symposium on Discrete Algorithms
City	San Francisco, CA, USA
Period	1/25/98 → 1/27/98

All Science Journal Classification (ASJC) codes

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

Cite this

@inproceedings{86502d9f6300479da3af038671b48c30,

title = "Polynomial-time approximation scheme for weighted planar graph TSP",

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.",

author = "Sanjeev Arora and Michelangelo Grigni and David Karger and Philip Klein and Andrzej Woloszyn",

year = "1998",

month = dec,

day = "1",

language = "English (US)",

pages = "33--41",

editor = "Anon",

booktitle = "Proceedings of the Annual ACM-SIAM Symposium on Discrete Algorithms",

publisher = "SIAM",

note = "Proceedings of the 1998 9th Annual ACM SIAM Symposium on Discrete Algorithms ; Conference date: 25-01-1998 Through 27-01-1998",

}

TY - GEN

T1 - Polynomial-time approximation scheme for weighted planar graph TSP

AU - Arora, Sanjeev

AU - Grigni, Michelangelo

AU - Karger, David

AU - Klein, Philip

AU - Woloszyn, Andrzej

PY - 1998/12/1

Y1 - 1998/12/1

N2 - 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.

AB - 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.

UR - http://www.scopus.com/inward/record.url?scp=0032266869&partnerID=8YFLogxK

UR - http://www.scopus.com/inward/citedby.url?scp=0032266869&partnerID=8YFLogxK

M3 - Conference contribution

AN - SCOPUS:0032266869

SP - 33

EP - 41

BT - Proceedings of the Annual ACM-SIAM Symposium on Discrete Algorithms

A2 - Anon, null

PB - SIAM

T2 - Proceedings of the 1998 9th Annual ACM SIAM Symposium on Discrete Algorithms

Y2 - 25 January 1998 through 27 January 1998

ER -

Polynomial-time approximation scheme for weighted planar graph TSP

Abstract

Other

All Science Journal Classification (ASJC) codes

Other files and links

Fingerprint

Cite this