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

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. 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.

Actions:

Download:	Postscript Download (132kB) | Preview
Editorial actions:	View Item (Login required)