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.
- 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 Scholar
- 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 Scholar
- Arora, S. 1998. Polynomial-time approximation schemes for Euclidean TSP and other geometric problems. J. ACM 45, 753--782. Google Scholar
- 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 Scholar
- Bajaj, C. 1998. The algebraic degree of geometric optimization problems. Disc. Comput. Geom. 3, 177--191. Google Scholar
- Barvinok, A. I. 1996. Two algorithmic results for the traveling salesman problem. Math. Oper. Res. 21, 65--84. Google Scholar
- 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 Scholar
- Cayley, A. 1889. A theorem on trees. Quart. J. Math. 23, 376--378.Google Scholar
- 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 Scholar
- Fekete, S. P., and Meijer, H. 2000. On minimum stars and maximum matchings. Disc. Comput. Geom. 23, 389--407.Google Scholar
- Fingerhut, J. A., Suri, S., and Turner, J. S. 1997. Designing least-cost nonblocking broadband networks. J. Algorithms 24, 287--309. Google Scholar
- 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 Scholar
- 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 Scholar
- Gusfield, D., Martel, C., and Fernandez-Baca, D. 1987. Fast algorithms for bipartite network flow. SIAM J. Comput. 16, 237--251. Google Scholar
- Hassin, R., and Rubinstein, S. 2002. A 7/8-approximation algorithm for metric Max TSP. Inf. Proc. Lett. 81, 247--251. Google Scholar
- Itai, A., Papadimitriou, C., and Swarcfiter, J. L. 1982. Hamilton paths in grid graphs. SIAM J. Comput. 11, 676--686.Google Scholar
- 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 Scholar
- Megiddo, N., and Tamir, A. 1993. Linear time algorithms for some separable quadratic programming problems. Oper. Res. Lett. 13, 203--211.Google Scholar
- 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 Scholar
- Papadimitriou, C. H. 1977. The Euclidean traveling salesman problem is NP-complete. Theoret. Comput. Sci. 4, 237--244.Google Scholar
- Papadimitriou, C. H., and Yannakakis, M. 1993. The Traveling Salesman problem with distances one and two. Math. Oper. Res. 18, 1--11. Google Scholar
- 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 Scholar
- 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 Scholar
- 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 Scholar
- 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 Scholar
- Tokuyama, T., and Nakano, J. 1995. Efficient algorithms for the Hitchcock transportation problem. SIAM J. Comput. 24, 563--578. Google Scholar
- 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 Scholar
- Zemel, E. 1984. An O(n) algorithm for the linear multiple choice knapsack problem and related problems. Inf. Proc. Lett. 18, 123--128. Google Scholar
Index Terms
The geometric maximum traveling salesman problem
Recommendations
The traveling salesman problem: low-dimensionality implies a polynomial time approximation scheme
STOC '12: Proceedings of the forty-fourth annual ACM symposium on Theory of computingThe Traveling Salesman Problem (TSP) is among the most famous NP-hard optimization problems. We design for this problem a randomized polynomial-time algorithm that computes a (1+µ)-approximation to the optimal tour, for any fixed µ>0, in TSP instances ...
Polynomial time approximation schemes for Euclidean traveling salesman and other geometric problems
We present a polynomial time approximation scheme for Euclidean TSP in fixed dimensions. For every fixed c > 1 and given any n nodes in ℛ2, a randomized version of the scheme finds a (1 + 1/c)-approximation to the optimum traveling salesman tour in O(n(...
Clique Tree Inequalities and the Symmetric Travelling Salesman Problem
The linear programming cutting plane approach for solving the travelling salesman problem has recently proven to be highly successful, cf. Crowder and Padberg Crowder, H. P., M. W. Padberg. 1980. Solving large-scale symmetric travelling salesman ...
Comments