skip to main content
article

The geometric maximum traveling salesman problem

Published:01 September 2003Publication History
Skip Abstract Section

Abstract

We consider the traveling salesman problem when the cities are points in ℝd for some fixed d and distances are computed according to geometric distances, determined by some norm. We show that for any polyhedral norm, the problem of finding a tour of maximum length can be solved in polynomial time. If arithmetic operations are assumed to take unit time, our algorithms run in time O(nf-2 log n), where f is the number of facets of the polyhedron determining the polyhedral norm. Thus, for example, we have O(n2 log n) algorithms for the cases of points in the plane under the Rectilinear and Sup norms. This is in contrast to the fact that finding a minimum length tour in each case is NP-hard. Our approach can be extended to the more general case of quasi-norms with a not necessarily symmetric unit ball, where we get a complexity of O(n2f-2 log n).For the special case of two-dimensional metrics with f = 4 (which includes the Rectilinear and Sup norms), we present a simple algorithm with O(n) running time. The algorithm does not use any indirect addressing, so its running time remains valid even in comparison based models in which sorting requires Ω(n log n) time. The basic mechanism of the algorithm provides some intuition on why polyhedral norms allow fast algorithms.Complementing the results on simplicity for polyhedral norms, we prove that, for the case of Euclidean distances in ℝd for d ≥ 3, the Maximum TSP is NP-hard. This sheds new light on the well-studied difficulties of Euclidean distances.

References

  1. Ahuja, R. K., Orlin, J. B., Stein, C., and Tarjan, R. E. 1994. Improved algorithms for bipartite network flow. SIAM J. Comput. 23, 906--933. Google ScholarGoogle Scholar
  2. Arkin, E. M., Chiang, Y.-J, Mitchell, J. S. B., Skiena, S. S., and Yang, T.-C. 1997. On the maximum scatter TSP. In Proceedings of the 8th Annual ACM-SIAM Symposium on Discrete Algorithms (SODA 97). ACM New York, 211--220. Google ScholarGoogle Scholar
  3. Arora, S. 1998. Polynomial-time approximation schemes for Euclidean TSP and other geometric problems. J. ACM 45, 753--782. Google ScholarGoogle Scholar
  4. Arora, S., Lund, C., Motwani, R., Sudan, M., and Szegedy, M. 1998. Proof verification and hardness of approximation problems. J. ACM 45, 501--555. Google ScholarGoogle Scholar
  5. Bajaj, C. 1998. The algebraic degree of geometric optimization problems. Disc. Comput. Geom. 3, 177--191. Google ScholarGoogle Scholar
  6. Barvinok, A. I. 1996. Two algorithmic results for the traveling salesman problem. Math. Oper. Res. 21, 65--84. Google ScholarGoogle Scholar
  7. Blum, M., Floyd, R. W., Pratt, V. R., Rivest, R. L., and Tarjan, R. E. 1972. Time bounds for selection. J. Comput. Syst. Sci. 7, 448--461.Google ScholarGoogle Scholar
  8. Cayley, A. 1889. A theorem on trees. Quart. J. Math. 23, 376--378.Google ScholarGoogle Scholar
  9. Cormen, T. H., Leiserson, E. L., Rivest, R. L., and Stein, C. 2001. Introduction to Algorithms, 2nd ed. MIT Press, Cambridge, Mass., p. 195. Google ScholarGoogle Scholar
  10. Fekete, S. P., and Meijer, H. 2000. On minimum stars and maximum matchings. Disc. Comput. Geom. 23, 389--407.Google ScholarGoogle Scholar
  11. Fingerhut, J. A., Suri, S., and Turner, J. S. 1997. Designing least-cost nonblocking broadband networks. J. Algorithms 24, 287--309. Google ScholarGoogle Scholar
  12. Garey, M. R., Graham, R. L., and Johnson, D. S. 1976a. Some NP-complete geometric problems. In Proceedings of the 8th ACM Symposium on Theory of Computing (STOC 76). ACM New York, 10--22. Google ScholarGoogle Scholar
  13. Garey, M. R., Johnson, D. S., and Tarjan, R. E. 1976b. The planar Hamiltonian circuit problem is NP-complete. SIAM J. Comput. 5, 704--714.Google ScholarGoogle Scholar
  14. Gusfield, D., Martel, C., and Fernandez-Baca, D. 1987. Fast algorithms for bipartite network flow. SIAM J. Comput. 16, 237--251. Google ScholarGoogle Scholar
  15. Hassin, R., and Rubinstein, S. 2002. A 7/8-approximation algorithm for metric Max TSP. Inf. Proc. Lett. 81, 247--251. Google ScholarGoogle Scholar
  16. Itai, A., Papadimitriou, C., and Swarcfiter, J. L. 1982. Hamilton paths in grid graphs. SIAM J. Comput. 11, 676--686.Google ScholarGoogle Scholar
  17. Matsui, T. 1992. 'Linear time algorithm for the Hitchcock transportation problem with a fixed number of supply points. Optimization---Modeling and Algorithms. Cooperative Research Report 35. The Institute of Statistical Mathematics, Minami-Azabu, Minato-ku, Tokyo, Japan, 128--138.Google ScholarGoogle Scholar
  18. Megiddo, N., and Tamir, A. 1993. Linear time algorithms for some separable quadratic programming problems. Oper. Res. Lett. 13, 203--211.Google ScholarGoogle Scholar
  19. Mitchell, J. S. B. 1999. Guillotine subdivisions approximate polygonal subdivisions: Part II---A simple PTAS for geometric k-MST, TSP, and related problems. SIAM J. Comput. 28, 1298--1309. Google ScholarGoogle Scholar
  20. Papadimitriou, C. H. 1977. The Euclidean traveling salesman problem is NP-complete. Theoret. Comput. Sci. 4, 237--244.Google ScholarGoogle Scholar
  21. Papadimitriou, C. H., and Yannakakis, M. 1993. The Traveling Salesman problem with distances one and two. Math. Oper. Res. 18, 1--11. Google ScholarGoogle Scholar
  22. Serdyukov, A. I. 1987. An asymptotically exact algorithm for the Traveling Salesman problem for a maximum in Euclidean space" (Russian). Upravlyaemye Sistemy 27, 79--87.Google ScholarGoogle Scholar
  23. Serdyukov, A. I. 1991. Asymptotic properties of optimal solutions of extremal permutation problems in finite-dimensional normed spaces" (Russian). Metody Diskret. Analiz. 51, 105--111.Google ScholarGoogle Scholar
  24. Serdyukov, A. I. 1995. The Traveling Salesman Problem for a maximum in finite-dimensional real spaces" (Russian). Diskret. Anal. Issled. Oper. 2, 1, 50--56.Google ScholarGoogle Scholar
  25. Tamir, A., and Mitchell, J. S. B. 1998. A maximum b-matching problem arising from median location models with applications to the roommates problem. Math. Prog. 80, 171--194. Google ScholarGoogle Scholar
  26. Tokuyama, T., and Nakano, J. 1995. Efficient algorithms for the Hitchcock transportation problem. SIAM J. Comput. 24, 563--578. Google ScholarGoogle Scholar
  27. 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 (STOC). ACM, New York, 21--29. Google ScholarGoogle Scholar
  28. Zemel, E. 1984. An O(n) algorithm for the linear multiple choice knapsack problem and related problems. Inf. Proc. Lett. 18, 123--128. Google ScholarGoogle Scholar

Index Terms

  1. The geometric maximum traveling salesman problem

          Recommendations

          Comments

          Login options

          Check if you have access through your login credentials or your institution to get full access on this article.

          Sign in

          Full Access

          PDF Format

          View or Download as a PDF file.

          PDF

          eReader

          View online with eReader.

          eReader