Nearly linear time approximation schemes for Euclidean TSP and other geometric problems

Research output: Contribution to journalConference article

91 Scopus citations

Abstract

We present a randomized polynomial time approximation scheme for Euclidean TSP in R2 that is substantially more efficient than our earlier scheme in [2] (and the scheme of Mitchell [21]). For any fixed c>1 and any set of n nodes in the plane, the new scheme finds a (1+1/c)-approximation to the optimum traveling salesman tour in O(n(log n)O(c)) time. (Our earlier scheme ran in nO(c) time.) For points in Rd the algorithm runs in O(n(log n)(O(√dc))d-1) time. This time is polynomial (actually nearly linear) for ever fixed c, d. Designing such a polynomial-time algorithm was an open problem (our earlier algorithm in [2] ran in superpolynomial time for d ≥3). The algorithm generalizes to the same set of Euclidean problems handled by the previous algorithm, including Steiner Tree, k-TSP, k-MST, etc, although for k-TSP and k-MST the running time gets multiplied by k. We also use our ideas to design nearly-linear time approximation schemes for Euclidean versions of problems that are known to be in P, such as Minimum Spanning Tree and Min Cost Perfect Matching. All our algorithms can be derandomized, though the running time then increases by O(nd) in Rd. They also have simple parallel implementations (say, in NC2).

Original languageEnglish (US)
Pages (from-to)554-563
Number of pages10
JournalAnnual Symposium on Foundations of Computer Science - Proceedings
StatePublished - Dec 1 1997
EventProceedings of the 1997 38th IEEE Annual Symposium on Foundations of Computer Science - Miami Beach, FL, USA
Duration: Oct 20 1997Oct 22 1997

All Science Journal Classification (ASJC) codes

  • Hardware and Architecture

Fingerprint Dive into the research topics of 'Nearly linear time approximation schemes for Euclidean TSP and other geometric problems'. Together they form a unique fingerprint.

  • Cite this