Simplicity and Hardness of the Maximum Traveling Salesman Problem under Geometric Distances

Fekete, Sandor P. (1999) Simplicity and Hardness of the Maximum Traveling Salesman Problem under Geometric Distances.
Published In: Soda'99 : Proceedings of the tenth annual ACM-SIAM Symposium on Discrete Algorithms ; Baltimore, Maryland, January 17 - 19, 1999 ACM 1999, pp. 337-345.


Recently, Barvinok, Johnson, Woeginger, and Woodroofe have shown that the Maximum TSP, i.e., the problem of finding a traveling salesman tour of maximum length, can be solved in polynomial time, provided that distances are computed according to a polyhedral norm in R d , for some fixed d. The most natural case of this class of problems arises for rectilinear distances in the plane R p , where the unit ball is a square. With the help of some additional improvements by Tamir, the method by Barvinok et al. yields an O(n 2 log n) algorithm for this case by making elegant use of geometry, graph theory, and optimization, including some rather powerful tools. In this paper, we present a simple algorithm with O(n) running time for computing the length of a longest tour for a set of points in the plane with rectilinear distances. The algorithm does not use any indirect addressing, so its running time remains valid even in comparison based models in which sorting requires Omega(n log n) time, which implies the same lower bound on verifying a Hamiltonian cycle. In addition, our approach gives a simple characterization of all optimal solutions. These results give a good idea what makes the (polyhedral) max TSP so much easier than its minimization counterpart. Resolving the complexity status of the max TSP for Euclidean distances in spaces of fixed dimension has been stated by Barvinok et al. as a main open problem. In this paper, the results on simplicity are complemented by a proof that the Maximum TSP under Euclidean distances in R d for any fixed d >= 3 is NP-hard, shedding new light on the well-studied difficulties of Euclidean distances. In addition, our result implies NP-hardness of the Maximum TSP under polyhedral norms if the number k of facets of the unit ball is not fixed. As a corollary, we get NP-hardness of the Maximum Scatter TSP for geometric instances, where the objective is to find a tour that maximizes the shortest edge. This resolves a conjecture by Arkin, Chiang, Mitchell, Skiena, and Yang in the affirmative.

Download: [img] Postscript - Preprinted Version
Download (321kB) | Preview
Editorial actions: View Item View Item (Login required)
Deposit Information:
ZAIK Number: zpr98-329
Depositing User: Archive Admin
Date Deposited: 02 Apr 2001 00:00
Last Modified: 19 Dec 2011 09:45