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: Contribution to conference › Paper › peer-review

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)
Pages	33-41
Number of pages	9
State	Published - 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

Software
General Mathematics

Cite this

@conference{44ab812fc99e4f9f95cd2367048d991c,

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

language = "English (US)",

pages = "33--41",

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

}

TY - CONF

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

Y1 - 1998

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 - Paper

AN - SCOPUS:0032266869

SP - 33

EP - 41

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