Polynomial time approximation schemes for Euclidean traveling salesman and other geometric problems

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 ℛ², 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(√c))^d-1). For every fixed c, d the running time is n · poly(logn), 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 ℓ_p for p ≥ 1 or other Minkowski norms). They also have simple parallel (i.e., NC) implementations.

References

1. AGARWAL, P., EDELSBRUNNER, H., SCHWARTZKOPF, 0., AND WELZL, E. 1991. Euclidean MST and bichromic closest pairs. Disc. Comput. Geom. 6, 407-422.
2. APPLEGATE, D., BIXBY, R., CHVATAL, V., AND COOK, W. 1995. Finding cuts in the TSP (a preliminary report). Report 95-05. DIMACS, Rutgers Univ., New Brunswick, N.J.
3. ARORA, S. 1996. Polynomial-time approximation schemes for Euclidean TSP and other geometric problem. In Proceedings of the 37th Annual IEEE Symposium on Foundations of Computer Science. IEEE Computer Society Press, Los Alamitos, Calif., pp. 2-12.
4. ARORA, S., GRIGNI, M., KARGER, D., KLEIN, P., AND WOLOSZYN, A. 1998. A polynomial-time approximation scheme for weighted planar graph TSP. In Proceedings of the 9th Annual ACM- SIAM Symposium on Discrete Algorithms. ACM, New York, pp. 33-41.
5. ARORA, S., LUND, C., MOTWANI, R., SUDAN, M., AND SZEGEDY, M. 1992. Proof verification and interactability of approximation problems. In Proceedings of the 33rd Annual IEEE Symposium on Foundations of Computer Science. IEEE Computer Society Press, Los Alamitos, Calif., pp. 13-22.
6. ARORA, S., RAGHAVAN, P., AND RAO, S. 1998. Approximation schemes for the Euclidean kmedians and related problems. In Proceedings of the 30th Annual ACM Symposium on Theory of Computing (Dallas, Tex., May 23-26). ACM, New York, pp. 106-113.
7. ARORA, S., AND SAFRA, S. 1992. Probabilistic checking of proofs: A new characterization of NP. In Proceedings of the 33rd IEEE Symposium on Foundations of Computer Science. IEEE Computer Society Press, Los Alamitos, Calif., pp. 2-12.
8. ASANO, T., KATOH, N., TAMAKI, H., AND TOKUYAMA, T. 1997. Covering points in the plane by k-tours: Towards a polynomial time approximation scheme for general k. In Proceedings of the 29th Annual ACM Symposium on Theory of Computing (El Paso, Tex., May 4-6). ACM, New York, pp. 275-283.
9. BEARDWOOD, J., HALTON, J. H., AND HAMMERSLEY, J.M. 1959. The shortest path through many points. Proc. Cambridge Philos. Sco. 55, 299-327.
10. BENTLEY, J. 1992. Fast algorithms for geometric traveling salesman problem. ORSA J. Comput. 4, 387-411.
11. BERN, M., AND EPPSTEIN, D. 1996. Approximation algorithms for geometric problems. In Approximation Algorithms for NP-Hard Problems. PWS Publishing, Boston, Mass.
12. BERN, M., EPPSTEIN, D., AND TENG, S.-H. 1993. Parallel construction of quadtree and quality triangulations. In Proceedings of the 3rd WADS, Lecture Notes in Computer Science, vol. 709. Springer-Verlag, New York, pp. 188-199.
13. BEAN, M., AND PLASSMANN, P. 1989. The Steiner problem with edge lengths 1 and 2. Inf. Proc. Lett. 32, 171-176.
14. BLUM, A., CHALASANI, P., AND VEMPALA, S. 1995. A constant-factor approximation for the k-MST problem in the plane. In Proceedings of the 27th Annual ACM Symposium on Theorem of Computing (Las Vegas, Nev., May 29-June 1). ACM, New York, pp. 294-302.
15. CHANDRA, B., KARLOFF, H., AND TOVEY, C. 1994. New results for the old k-OPT algorithm for the TSP. In Proceedings of the 5th Annual ACM-SIAM Symposium on Discrete Algorithms. ACM, New York, pp. 150-159.
16. CHRISTOFIDES, N. 1976. Worst-case analysis of a new heuristic for the traveling salesman problem. In Symposium on New Directions and Recent Results in Algorithms and Complexity, J. F. Traub, ed. Academic Press, Orlando, Fla., p. 441.
17. Du, D. Z., AND HWANG, F.K. 1992. A proof of Gilbert-Pollack's conjecture on the Steiner ratio. Algorithmica 7, 121-135.
18. EPPSTEIN, D. 1998. Faster geometric k-point MST approximation. CGTA, to appear.
19. EPPSTEIN, D., AND ERICKSON, J. 1994. Iterated nearest neighbors and finding minimal polytopes. Disc. Comput. Geom. 11, 321-350.
20. FEIGE, U., GOLDWASSER, S., LOVASZ, L., SAFRA, S., AND SZEGEDY, M. 1991. Approximating clique is almost NP-complete. In Proceedings of the 32nd IEEE Symposium on Foundations of Computer Science. IEEE Computer Society Press, Los Alamitos, Calif., pp. 2-12.
21. FERNANDEZ DE LA VEGA, W., AND LUEKER, G.S. 1981. Bin packing can be solved within 1 + e in linear time. Combinatorica 1, 4, 349-355.
22. FISCHETTI, M., HAMACHER, H. W., JORNSTEN, K., AND MAFFIOLI, F. 1994. Weighted k-cardinality trees: Complexity and polyhedral structure. Networks 32, 11-21.
23. GAREY, M. R., GRAHAM, R. L., AND JOHNSON, D.S. 1976. Some NP-complete geometric problems. In Proceedings of the 8th Annual ACM Symposium on Theory of Computing (Hershey, Pa., May 3-5). ACM, New York, pp. 10-22.
24. GARG, N. 1996. A 3-approximation for the minimum tree spanning k vertices. In Proceedings of the 37th Annual IEEE Foundations of Computer Science. IEEE Computer Society Press, Los Alamitos, Calif., pp. 302-310.
25. GILBERT, E. N., AND POLLAK, R.O. 1968. Steiner minimal trees. SIAM J. Appl. Math. 16, 1-29.
26. GOEMANS, M. 1995. Worst-case comparison of valid inequalities for the TSP. Math. Prog. 69, 336-349.
27. GRAHAM, R. L. 1966. Bounds for certain multiprocessing anomalies. Bell Syst. Tech. J. 45, 1563-1581.
28. GRIGNI, M., KOUTSOUPIAS, E., AND PAPDIMITRIOU, C. H. 1995. An approximation scheme for planar graph TSP. In Proceedings of the 36th Annual IEEE Symposium on Foundations of Computer Science. IEEE Computer Society Press, Los Alamitos, Calif., pp. 640-645.
29. HOCHBAUM, D., ED. 1996. Approximation Algorithms for NP-Hard Problems. PWS Publishing, Boston, Mass.
30. IBARRA, O. H., AND KIN, C.E. 1975. Fast approximation algorithms for the knapsack and sum of subsets problems. J. ACM 22, 4 (Oct.) 463-468.
31. JOHNSON, D.S. 1974. Approximation algorithms for combinatorial problems. J. Comput. Syst. Sci. 9, 256-278.
32. JOHNSON, D. S., AND MCGEOCH, L.A. 1997. The traveling salesman problem: A case study in local optimization. In Local Search in Combinatorial Optimization, E. H. L. Aarts and J. K. Lenstra, eds. Wiley, New York.
33. JOHNSON, D. S., PAPADIMITRIOU, C., AND YANNAKAKIS, M. 1988. How easy is local search. J. Comput. Syst. Sci. 37, 79-100.
34. JOHNSON, W. B., AND LINDENSTRAUSS, J. 1984. Extensions of Lipschitz mappings into Hilbert space. Contemp. Math. 26, 189-206.
35. KARMARKAR, N., AND KARP, R. M. 1982. An efficient approximation scheme for the onedimensional bin-packing problem. In Proceedings of the 23rd Annual IEEE Symposium on Foundations of Computer Science. IEEE Computer Society Press, Los Alamitos, Calif., pp. 312-320.
36. KARP, R. M. 1972. Reducibility among combinatorial problems. In Complexity of Computer Computations, R. E. Miller and J. W. Thatcher, eds. Advances in Computer Research, Plenum Press, New York, pp. 85-103.
37. KARP, R.M. 1977. Probabilistic analysis of partitioning algorithms for the TSP in the plane. Math. Oper. Res. 2, 209-224.
38. KHULLER, S., RAGHAVACHARI, B., AND YOUNG, N. 1996. Low degree spanning tree of small weight. SIAM J. Comput. 25, 355-368.
39. KRENTEL, M.W. 1989. Structure in locally optimal solutions. In Proceedings of the 30th Annual IEEE Symposium on Foundation of Computer Science. IEEE Computer Society Press, Los Alamitos, Calif., pp. 216-221.
40. LAWLER, E. L., LENSTRA, J. K., RINNOOY KAN, A. H. G., AND SHMOYS, D.B. 1985. The traveling salesman problem. Wiley, New York.
41. LIN, S. 1965. Computer solutions for the traveling salesman problem. Bell Syst. Tech J. 44, 2245-2269.
42. LIN, S., AND KERNIGHAN, B.W. 1973. An effective heuristic algorithm for the traveling salesman problem. Oper. Res. 21,498-516.
43. MATA, C. S., AND MITCHELL, J. B. 1995. Approximation algorithms for geometric tour and network design problems. In Proceedings of the llth Annual ACM Symposium on Computational Geometry (Vancouver, B.C., Canada, June 5-7). ACM, New York, pp. 360-369.
44. MELZAK, Z.A. 1961. On the problem of Steiner. Canad. Math Bull 4, 143-148.
45. MITCHELL, J. S. B. 1996. Guillotine subdivisions approximate polygonal subdivisions: A simple new method for the geometric k-MST problem. In Proceedings of the 6th Annual ACM-SIAM Symposium on Discrete Algorithms (Atlanta, Ga., Jan. 28-30). ACM, New York, pp. 402-408.
46. MITCHELL, J. S.B. 1998. Guillotine subdivisions approximate polygonal subdivisions: Part II-A simple PTAS for geometric k-MST, TSP, and related problems. SIAM J. Comput., to appear.
47. PAPADIMITRIOU, C.H. 1977. Euclidean TSP is NP-complete. Theoret. Comput. Sci. 4, 237-244.
48. PAPADIMITRIOU, C. H. 1992. The complexity of the Lin-Kernighan heuristic for the traveling salesman problem. SIAM J. Comput. 21, 3, 450-465.
49. PAPADIMITRIOU, C. H., AND YANNAKAKIS, M. 1984. The complexity of facets (and some facets of complexity). J. Comput. Syst. Sci. 28, 244-259.
50. PAPADIMITRIOU, C. H., AND YANNAKAKIS, M. 1991. Optimization, approximation and complexity classes. J. Comput. Syst. Sci. 43, 425-440.
51. RAO, S. B., AND SMITH, W. D. 1988. Approximating geometric graphs via "spanners" and "banyans". In Proceedings of the 30th ACM Symposium on the Theory of Computing (Dallas, Tex., May 23-26). ACM, New York, pp. 540-550.
52. REINELT, G. 1991. TSPLIB-A traveling salesman problem library. ORSA J. Comput. 3, 376-384.
53. SAHNI, S., AND GONZALES, T. 1976. P-complete approximation problems. J. ACM 23, 555-565.
54. SHMOYS, D. B., AND WILLIAMSON, D.P. 1990. Analyzing the Held-Karp TSP bound: A monotonicity property with application. Inf. Proc. Lett. 35, 281-285.
55. SMITH, W.D. 1988. Finding the optimum N-city traveling salesman tour in the Euclidean plan in subexponential time and polynomial space. Manuscript.
56. TREVISAN, L. 1997. When Hamming meets Euclid: The approximability of geometric TSP and MST. In Proceedings of the 29th Annual ACM Symposium on Theory of Computing (El Paso, Tex., Mar. 4-6). ACM, New York, pp. 21-39.
57. VAIDYA, P. 1988. Geometry helps in matching. SIAM J. Comput. 18, 1201-1225.
58. VAIDYA, P. 1989. Approximate minimum weight matching on k-dimensional spaces. Algorithmica 4, 569-583.
59. WANG, K. 1996. Is the m parameter in Arora's TSP algorithm the best possible? Junior Project, Princeton University, Princeton, N.J.
60. WOLSEY, L.A. 1980. Heuristic analysis, linear programming and branch and bound. Math. Prog. Study 13, 121-134.
61. ZELIKOVSKY, A. Z. 1993. An 11/6-approximation algorithm for the network Steiner Problem. Algorithmica 9, 463-470.
62. ZELIKOVSKY, A.Z. 1996. Better approximation bounds for the network and Euclidean Steiner tree problems. Tech. Rep. CS-96-06. Univ. Virginia.

Index Terms

• Mathematics of computing

  • Discrete mathematics

    • Graph theory

      • Paths and connectivity problems

      • Trees

• Theory of computation

  • Design and analysis of algorithms

    • Approximation algorithms analysis

      • Routing and network design problems

  • Randomness, geometry and discrete structures

    • Computational geometry