## Abstract

We present a polynomial time approximation scheme for Euclidean TSP in fixed dimensions. For every fixed c > 1 and given any n nodes in ℛ^{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 ℛ^{d}, the running time increases to O(n(log n)^{(O(√dc))g-1}). For every fixed c, d the running time is n·poly(log n), that is nearly linear in n. The algorithm 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-approximation 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 ℓ_{p} for p ≥ 1 or other Minkowski norms). They also have simple parallel (i.e., NC) implementations.

Original language | English (US) |
---|---|

Pages (from-to) | 753-782 |

Number of pages | 30 |

Journal | Journal of the ACM |

Volume | 45 |

Issue number | 5 |

DOIs | |

State | Published - Sep 1998 |

## All Science Journal Classification (ASJC) codes

- Software
- Control and Systems Engineering
- Information Systems
- Hardware and Architecture
- Artificial Intelligence

## Keywords

- Algorithms
- Approximation Algorithms
- F.2.2 [Analysis of Algorithms and Problem Complexity]: Geometrical problems and computations, Routing and layout
- G.2.2 [Graph Theory]: Path and circuit problems, Trees
- Theory
- Traveling Salesman Problem