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.


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 NP-hard, shedding new light on the well-studied difficulties of Euclidean distances.

Full text not available from this repository.
Editorial actions: View Item View Item (Login required)
Deposit Information:
ZAIK Number: zpr98-333
Depositing User: Archive Admin
Date Deposited: 02 Apr 2001 00:00
Last Modified: 16 Jan 2012 16:39