Nearly linear time approximation schemes for Euclidean TSP and other geometric problems
| Author(s) : | Sanjeev Arora, |
| Publisher : | N/A |
| Publication Date : | 1997 |
| ISSN : | N/A |
| Abstract : | We present a randomized polynomial time approximation scheme for Euclidean TSP in! 2 that is substantially more efficient than our earlier scheme in [3] (and the scheme of Mitchell [40]). 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 n O(c), |