## Abstract

We present a polynomial time approximation scheme for Euclidean TSP in R^{2}. Given any n nodes in the plane and ε>O, the scheme finds a (1+ε)-approximation to the optimum traveling salesman tour in time n^{O(1/ε)}. When the nodes are in R^{d}, the running time increases to n^{O(log(d-2)n)/ε(d-1)}. 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 a host of other Euclidean problems, including Steiner Tree, k-TSP, Minimum degree-k spanning tree, k-MST, etc. (This list may get longer; our techniques are fairly general.) The previous best approximation algorithms for all these problems achieved a constant-factor approximation. All our algorithms also work, with almost no modification, when distance is measured using any geometric norm (such as l_{p} for p≥1 or other Minkowski norms).

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

Pages (from-to) | 2-11 |

Number of pages | 10 |

Journal | Annual Symposium on Foundations of Computer Science - Proceedings |

State | Published - 1996 |

Event | Proceedings of the 1996 37th Annual Symposium on Foundations of Computer Science - Burlington, VT, USA Duration: Oct 14 1996 → Oct 16 1996 |

## All Science Journal Classification (ASJC) codes

- Hardware and Architecture