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 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(logn), that is nearly linear in n. The algorithmm can be derandomized, but this increases the running time by a factor O(nd). 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: Pankaj K. Agarwal , Herbert Edelsbrunner , Otfried Schwarzkopf , Emo Welzl, Euclidean minimum spanning trees and bichromatic closest pairs, Discrete & Computational Geometry, v.6 n.5, p.407-422, 1991 [doi>10.1007/BF02574698]
• 2: D. Applegate , R. Bixby , V. Chvatal , B. Cook, Finding Cuts in the TSP (A preliminary report), Certer for Discrete Mathematics & Theoretical Computer Science, 1995
• 3: S. Arora, Polynomial time approximation schemes for Euclidean TSP and other geometric problems, Proceedings of the 37th Annual Symposium on Foundations of Computer Science, p.2, October 14-16, 1996
• 4: Sanjeev Arora , Michelangelo Grigni , David Karger , Philip Klein , Andrzej Woloszyn, A polynomial-time approximation scheme for weighted planar graph TSP, Proceedings of the ninth annual ACM-SIAM symposium on Discrete algorithms, p.33-41, January 25-27, 1998, San Francisco, California, United States
• 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: Sanjeev Arora , Prabhakar Raghavan , Satish Rao, Approximation schemes for Euclidean k-medians and related problems, Proceedings of the thirtieth annual ACM symposium on Theory of computing, p.106-113, May 24-26, 1998, Dallas, Texas, United States [doi>10.1145/276698.276718]
• 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: Tetsuo Asano , Naoki Katoh , Hisao Tamaki , Takeshi Tokuyama, Covering points in the plane by k-tours: towards a polynomial time approximation scheme for general k, Proceedings of the twenty-ninth annual ACM symposium on Theory of computing, p.275-283, May 04-06, 1997, El Paso, Texas, United States [doi>10.1145/258533.258602]
• 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: Marshall Bern , David Eppstein, Approximation algorithms for geometric problems, Approximation algorithms for NP-hard problems, PWS Publishing Co., Boston, MA, 1996
• 12: Marshall W. Bern , David Eppstein , Shang-Hua Teng, Parallel Construction of Quadtrees and Quality Triangulations, Proceedings of the Third Workshop on Algorithms and Data Structures, p.188-199, August 11-13, 1993
• 13: Marshall Bern , Paul Plassmann, The steiner problem with edge lengths 1 and 2,, Information Processing Letters, v.32 n.4, p.171-176, Sept 1, 1989 [doi>10.1016/0020-0190(89)90039-2]
• 14: Avrim Blum , Prasad Chalasani , Santosh Vempala, A constant-factor approximation for the k-MST problem in the plane, Proceedings of the twenty-seventh annual ACM symposium on Theory of computing, p.294-302, May 29-June 01, 1995, Las Vegas, Nevada, United States [doi>10.1145/225058.225143]
• 15: Barun Chandra , Howard Karloff , Craig Tovey, New results on the old k-opt algorithm for the TSP, Proceedings of the fifth annual ACM-SIAM symposium on Discrete algorithms, p.150-159, January 23-25, 1994, Arlington, Virginia, United States
• 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: David Eppstein, Faster geometric k-point MST approximation, Computational Geometry: Theory and Applications, v.8 n.5, p.231-240, Oct. 1997 [doi>10.1016/S0925-7721(96)00021-1]
• 19: EPPSTEIN, D., AND ERICKSON, J. 1994. Iterated nearest neighbors and finding minimal polytopes. Disc. Comput. Geom. 11, 321-350.
• 20: U. Feige , S. Goldwasser , L. Lovász , S. Safra , M. Szegedy, Approximating clique is almost NP-complete (preliminary version), Proceedings of the 32nd annual symposium on Foundations of computer science, p.2-12, September 1991, San Juan, Puerto Rico [doi>10.1109/SFCS.1991.185341]
• 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: M. R. Garey , R. L. Graham , D. S. Johnson, Some NP-complete geometric problems, Proceedings of the eighth annual ACM symposium on Theory of computing, p.10-22, May 03-05, 1976, Hershey, Pennsylvania, United States [doi>10.1145/800113.803626]
• 24: N. Garg, A 3-approximation for the minimum tree spanning k vertices, Proceedings of the 37th Annual Symposium on Foundations of Computer Science, p.302, October 14-16, 1996
• 25: GILBERT, E. N., AND POLLAK, R.O. 1968. Steiner minimal trees. SIAM J. Appl. Math. 16, 1-29.
• 26: Michel X. Goemans, Worst-case comparison of valid inequalities for the TSP, Mathematical Programming: Series A and B, v.69 n.2, p.335-349, Aug. 25, 1995
• 27: GRAHAM, R. L. 1966. Bounds for certain multiprocessing anomalies. Bell Syst. Tech. J. 45, 1563-1581.
• 28: M. Grigni , E. Koutsoupias , C. Papadimitriou, An approximation scheme for planar graph TSP, Proceedings of the 36th Annual Symposium on Foundations of Computer Science (FOCS'95), p.640, October 23-25, 1995
• 29: Dorit S. Hochbaum, Approximation algorithms for NP-hard problems, PWS Publishing Co., Boston, MA, 1996
• 30: Oscar H. Ibarra , Chul E. Kim, Fast Approximation Algorithms for the Knapsack and Sum of Subset Problems, Journal of the ACM (JACM), v.22 n.4, p.463-468, Oct. 1975 [doi>10.1145/321906.321909]
• 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: David S. Johnson , Christos H. Papadimtriou , Mihalis Yannakakis, How easy is local search?, Journal of Computer and System Sciences, v.37 n.1, p.79-100, August 1988 [doi>10.1016/0022-0000(88)90046-3]
• 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: Samir Khuller , Balaji Raghavachari , Neal Young, Low-Degree Spanning Trees of Small Weight, SIAM Journal on Computing, v.25 n.2, p.355-368, February 1996 [doi>10.1137/S0097539794264585]
• 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: Cristian S. Mata , Joseph S. B. Mitchell, Approximation algorithms for geometric tour and network design problems (extended abstract), Proceedings of the eleventh annual symposium on Computational geometry, p.360-369, June 05-07, 1995, Vancouver, British Columbia, Canada [doi>10.1145/220279.220318]
• 44: MELZAK, Z.A. 1961. On the problem of Steiner. Canad. Math Bull 4, 143-148.
• 45: Joseph S. B. Mitchell, Guillotine subdivisions approximate polygonal subdivisions: a simple new method for the geometric k-MST problem, Proceedings of the seventh annual ACM-SIAM symposium on Discrete algorithms, p.402-408, January 28-30, 1996, Atlanta, Georgia, United States
• 46: Joseph S. B. Mitchell, Guillotine Subdivisions Approximate Polygonal Subdivisions: A Simple Polynomial-Time Approximation Scheme for Geometric TSP, k-MST, and Related Problems, SIAM Journal on Computing, v.28 n.4, p.1298-1309, Aug. 1999 [doi>10.1137/S0097539796309764]
• 47: PAPADIMITRIOU, C.H. 1977. Euclidean TSP is NP-complete. Theoret. Comput. Sci. 4, 237-244.
• 48: Christos H. Papadimitriou, The complexity of the Lin-Kernighan heuristic for the traveling salesman problem, SIAM Journal on Computing, v.21 n.3, p.450-465, June 1992 [doi>10.1137/0221030]
• 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: Satish B. Rao , Warren D. Smith, Approximating geometrical graphs via “spanners” and “banyans”, Proceedings of the thirtieth annual ACM symposium on Theory of computing, p.540-550, May 24-26, 1998, Dallas, Texas, United States [doi>10.1145/276698.276868]
• 52: REINELT, G. 1991. TSPLIB-A traveling salesman problem library. ORSA J. Comput. 3, 376-384.
• 53: Sartaj Sahni , Teofilo Gonzalez, P-Complete Approximation Problems, Journal of the ACM (JACM), v.23 n.3, p.555-565, July 1976 [doi>10.1145/321958.321975]
• 54: D. B. Shmoys , D. P. Williamson, Analyzing the Held-Karp TSP bound: a monotonicity property with application, Information Processing Letters, v.35 n.6, p.281-285, Sep. 1990 [doi>10.1016/0020-0190(90)90028-V]
• 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: Luca Trevisan, When Hamming meets Euclid: the approximability of geometric TSP and MST (extended abstract), Proceedings of the twenty-ninth annual ACM symposium on Theory of computing, p.21-29, May 04-06, 1997, El Paso, Texas, United States [doi>10.1145/258533.258541]
• 57: P. M. Vaidya, Geometry helps in matching, SIAM Journal on Computing, v.18 n.6, p.1201-1225, Dec. 1989 [doi>10.1137/0218080]
• 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: Alexander Zelikovsky, Better approximation bounds for the network and Euclidean Steiner tree problems, University of Virginia, Charlottesville, VA, 1996

INDEX TERMS

Primary Classification:
  F. Theory of Computation
  F.2 ANALYSIS OF ALGORITHMS AND PROBLEM COMPLEXITY
      F.2.2 Nonnumerical Algorithms and Problems
          Subjects: Geometrical problems and computations

Additional Classification:
  F. Theory of Computation
  F.2 ANALYSIS OF ALGORITHMS AND PROBLEM COMPLEXITY
      F.2.2 Nonnumerical Algorithms and Problems
          Subjects: Routing and layout

  G. Mathematics of Computing
  G.2 DISCRETE MATHEMATICS
      G.2.2 Graph Theory
          Subjects: Trees; Path and circuit problems

General Terms:
Algorithms, Theory

Keywords:
Steiner problem, approximation algorithms, matching, network design, traveling salesman problem