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

Research output: Chapter in Book/Report/Conference proceedingConference contribution


We present a randomized polynomial time approximation scheme for Euclidean TSP in (Formula Presented) that is substantially more efficient than our earlier scheme in Polynomial-time Approximation Schemes for Euclidean TSP and other Geometric Problems, Proceedings of IEEE FOCS 1996, pp 2-11 (and the scheme of Mitchell, which he discovered a few months later). 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)co(c) time. (Our earlier scheme ran in n o(c) time.) For points in (Formula Presented) the algorithm runs in O(n(logn)o(√dc))d-1) time. This time is polynomial (actually nearly linear) for every fixed c, d; designing such a polynomial-time algorithm was an open problem (our earlier algorithm ran in quasipolynomial time for d ≥ 3). The algorithm generalizes to the same set of Euclidean problems handled by the previous algorithm, including Steiner Tree, k-TSP, Minimum degree-restricted spanning tree, 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 also work, with almost no modification, when distance is measured using any geometric norm (such as ℓp for p ≥ 1 or other Minkowski norms). They also have simple parallel implementations (say, in NC2). We design the PTAS by showing that the plane can be recursively partitioned (using a randomized variant of the quadtree) such that some (1 + 1/c)-approximate salesman tour crosses each line of the partition at most r = O(c) times Such a tour can be found by dynamic programming. For each line in the partition the algorithm first "guesses" where the tour crosses this line and the order in which those crossings occur. Then the algorithm recurses independently on the two sides of the line. There are only n log n distinct regions in the partition. Within each region it is sufficient to "guess" the places where the tour crosses the boundary quite coarsely. The dynamic programming then takes only (O(log n))o(r) = (log n) o(c) time per region, for a total running time of n. (log n) o(c).

Original languageEnglish (US)
Title of host publicationRandomization and Approximation Techniques in Computer Science - International Workshop, RANDOM 1997, Proceedings
EditorsJosé Rolim
PublisherSpringer Verlag
ISBN (Print)3540632484, 9783540632481
StatePublished - Jan 1 1997
EventInternational Workshop on Randomization and Approximation Techniques in Computer Science, RANDOM 1997 - Bologna, Italy
Duration: Jul 11 1997Jul 12 1997

Publication series

NameLecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)
ISSN (Print)0302-9743
ISSN (Electronic)1611-3349


OtherInternational Workshop on Randomization and Approximation Techniques in Computer Science, RANDOM 1997

All Science Journal Classification (ASJC) codes

  • Computer Science(all)
  • Theoretical Computer Science

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