Finding maximum length tours under Euclidean norms

Fekete, Sandor P. (1998) Finding maximum length tours under Euclidean norms.
Technical Report , 5 p.


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. They stated as an open problem to resolve the complexity of finding a maximum length tour under Euclidean distances in a space of fixed dimension. In this paper it is shown that the Maximum TSP under Euclidean distances in R d for any fixed d > 2 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, and NP-hardness of the Maximum Scatter TSP for geometric instances, where the objective is to find a tour that maximizes the shortest edge.

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