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 ACMSIAM Symposium on Discrete Algorithms ; Baltimore, Maryland, January 17  19, 1999 ACM 1999, pp. 337345.
Abstract
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 NPhard, shedding new light on the wellstudied difficulties of Euclidean distances. In addition, our result implies NPhardness 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 NPhardness 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: 
Postscript
 Preprinted Version
Download (321kB)  Preview 

Editorial actions:  View Item (Login required) 
Item Type:  Proceedings article 

Citations:  24 (Google Scholar)  6 (Web of Science) 
Uncontrolled Keywords:  combinatorial optimization computational complexity Euclidean norm geometric optimization polyhedral norm traveling salesman problem 
Subjects: 

Divisions:  Institute of Computer Science > Computer Science Department  Prof. Dr. Schrader Mathematical Institute > Prof. Dr. Faigle 
Related URLs: 
ZAIK Number:  zpr98329 

Depositing User:  Archive Admin 
Date Deposited:  02 Apr 2001 00:00 
Last Modified:  19 Dec 2011 09:45 
URI:  http://earchive.informatik.unikoeln.de/id/eprint/329 