Finding maximum length tours under Euclidean norms
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.
Download: |
Download (132kB) | Preview |
---|---|
Editorial actions: | ![]() |
Item Type: | Paper (Technical Report) |
---|---|
Citations: | 0 (Google Scholar) | |
Uncontrolled Keywords: | combinatorial optimization computational complexity Euclidean norm geometric optimization polyhedral norm traveling salesman problem |
Subjects: |
|
Divisions: | Mathematical Institute |
Related URLs: |
ZAIK Number: | zpr98-317 |
---|---|
Depositing User: | Archive Admin |
Date Deposited: | 02 Apr 2001 00:00 |
Last Modified: | 19 Dec 2011 09:45 |
URI: | http://e-archive.informatik.uni-koeln.de/id/eprint/317 |