The Maximum Traveling Salesman Problem
Barvinok, A. and Fekete, Sandor P. and Johnson, David S. and Tamir, Arie and Woeginger, Gerhard J. and Woodroofe, D. (1998) The Maximum Traveling Salesman Problem.
Abstract
In this paper, we present a number of results on the Maximum TSP, i.e., the problem of finding a traveling salesman tour of maximum length. In particular, we show that the problem 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. We also 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. 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. 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.
Item Type:  Article 

Citations:  34 (Google Scholar)  
Uncontrolled Keywords:  combinatorial optimization computational complexity Euclidean norm geometric optimization polyhedral norm traveling salesman problem 
Subjects: 

Divisions:  UNSPECIFIED 
Related URLs: 
ZAIK Number:  zpr98333 

Depositing User:  Archive Admin 
Date Deposited:  02 Apr 2001 00:00 
Last Modified:  16 Jan 2012 16:39 
URI:  http://earchive.informatik.unikoeln.de/id/eprint/333 