TY - JOUR
T1 - Polynomial time approximation schemes for Euclidean TSP and other geometric problems
AU - Arora, Sanjeev
PY - 1996/12/1
Y1 - 1996/12/1
N2 - We present a polynomial time approximation scheme for Euclidean TSP in R2. Given any n nodes in the plane and ε>O, the scheme finds a (1+ε)-approximation to the optimum traveling salesman tour in time nO(1/ε). When the nodes are in Rd, the running time increases to nO(log(d-2)n)/ε(d-1). The previous best approximation algorithm for the problem (due to Christofides) achieves a 3/2-approximation in polynomial time. We also give similar approximation schemes for a host of other Euclidean problems, including Steiner Tree, k-TSP, Minimum degree-k spanning tree, k-MST, etc. (This list may get longer; our techniques are fairly general.) The previous best approximation algorithms for all these problems achieved a constant-factor approximation. All our algorithms also work, with almost no modification, when distance is measured using any geometric norm (such as lp for p≥1 or other Minkowski norms).
AB - We present a polynomial time approximation scheme for Euclidean TSP in R2. Given any n nodes in the plane and ε>O, the scheme finds a (1+ε)-approximation to the optimum traveling salesman tour in time nO(1/ε). When the nodes are in Rd, the running time increases to nO(log(d-2)n)/ε(d-1). The previous best approximation algorithm for the problem (due to Christofides) achieves a 3/2-approximation in polynomial time. We also give similar approximation schemes for a host of other Euclidean problems, including Steiner Tree, k-TSP, Minimum degree-k spanning tree, k-MST, etc. (This list may get longer; our techniques are fairly general.) The previous best approximation algorithms for all these problems achieved a constant-factor approximation. All our algorithms also work, with almost no modification, when distance is measured using any geometric norm (such as lp for p≥1 or other Minkowski norms).
UR - http://www.scopus.com/inward/record.url?scp=0030413554&partnerID=8YFLogxK
UR - http://www.scopus.com/inward/citedby.url?scp=0030413554&partnerID=8YFLogxK
M3 - Article
AN - SCOPUS:0030413554
SN - 0272-5428
SP - 2
EP - 11
JO - Annual Symposium on Foundations of Computer Science - Proceedings
JF - Annual Symposium on Foundations of Computer Science - Proceedings
ER -