TY - GEN
T1 - A linear time approximation scheme for Euclidean TSP
AU - Bartal, Yair
AU - Gottlieb, Lee Ad
PY - 2013
Y1 - 2013
N2 - The Traveling Salesman Problem (TSP) is among the most famous NP-hard optimization problems. The special case of TSP in bounded-dimensional Euclidean spaces has been a particular focus of research: The celebrated results of Arora [Aro98] and Mitchell [Mit99] - Along with subsequent improvements of Rao and Smith [RS98] - demonstrated a polynomial time approximation scheme for this problem, ultimately achieving a runtime of Od,ε(n log n). In this paper, we present a linear time approximation scheme for Euclidean TSP, with runtime Od,ε(n). This improvement resolves a 15 year old conjecture of Rao and Smith, and matches for Euclidean spaces the bound known for a broad class of planar graphs [Kle08].
AB - The Traveling Salesman Problem (TSP) is among the most famous NP-hard optimization problems. The special case of TSP in bounded-dimensional Euclidean spaces has been a particular focus of research: The celebrated results of Arora [Aro98] and Mitchell [Mit99] - Along with subsequent improvements of Rao and Smith [RS98] - demonstrated a polynomial time approximation scheme for this problem, ultimately achieving a runtime of Od,ε(n log n). In this paper, we present a linear time approximation scheme for Euclidean TSP, with runtime Od,ε(n). This improvement resolves a 15 year old conjecture of Rao and Smith, and matches for Euclidean spaces the bound known for a broad class of planar graphs [Kle08].
KW - Computations on discrete structures
KW - Geometrical problems and computations
UR - https://www.scopus.com/pages/publications/84893475149
U2 - 10.1109/FOCS.2013.80
DO - 10.1109/FOCS.2013.80
M3 - ???researchoutput.researchoutputtypes.contributiontobookanthology.conference???
AN - SCOPUS:84893475149
SN - 9780769551357
T3 - Proceedings - Annual IEEE Symposium on Foundations of Computer Science, FOCS
SP - 698
EP - 706
BT - Proceedings - 2013 IEEE 54th Annual Symposium on Foundations of Computer Science, FOCS 2013
PB - IEEE Computer Society
T2 - 54th Annual IEEE Symposium on Foundations of Computer Science, FOCS 2013
Y2 - 27 October 2013 through 29 October 2013
ER -