We present a polynomial time approximation scheme for Euclidean TSP in fixed dimensions. For every fixed  c  > 1 and given any  n  nodes in    R     2 , a randomized version of the scheme finds a (1 + 1/ c )-approximation to the optimum traveling salesman tour in  O(n (log  n )  O(c) )  time. When the nodes are in    R     d , the running time increases to  O(n (log  n ) (O(    d      c)) d-1 ). For every fixed  c,    d  the running time is  n  • poly(log n ), that is  nearly linear  in  n . The algorithmm can be derandomized, but this increases the running time by  a  factor  O(n d  ). The previous best approximation algorithm for the problem (due to Christofides) achieves a 3/2-aproximation in polynomial time.  We also give similar approximation schemes for some other NP-hard Euclidean problems: Minimum Steiner Tree,  k -TSP, and  k -MST. (The running times of the algorithm for  k -TSP and  k -MST involve an additional multiplicative factor  k .) The previous best approximation algorithms for all these problems    achieved a constant-factor approximation. We also give efficient approximation schemes for Euclidean Min-Cost Matching, a problem that can be solved exactly in polynomial time.  All our algorithms also work, with almost no modification, when distance is measured using any geometric norm (such as   e     p   for  p  ≥ 1 or other Minkowski norms). They also have simple parallel (i.e., NC) implementations.
['Sanjeev Arora']
Polynomial time approximation schemes for Euclidean traveling salesman and other geometric problems