Access Restriction

Author Barvinok, Alexander ♦ Fekete, Sndor P. ♦ Johnson, David S. ♦ Tamir, Arie ♦ Woeginger, Gerhard J. ♦ Woodroofe, Russ
Source ACM Digital Library
Content type Text
Publisher Association for Computing Machinery (ACM)
File Format PDF
Copyright Year ©2003
Language English
Subject Domain (in DDC) Computer science, information & general works ♦ Data processing & computer science
Subject Keyword Euclidean metric ♦ NP-hardness ♦ Traveling salesman problem ♦ Maximum scatter TSP ♦ Optimization ♦ Polyhedral metric ♦ Polynomial time
Abstract We consider the traveling salesman problem when the cities are points in $&##x211D;^{d}$ for some fixed $\textit{d}$ and distances are computed according to geometric distances, determined by some norm. We show that for any polyhedral norm, the problem of finding a tour of $\textit{maximum}$ length can be solved in polynomial time. If arithmetic operations are assumed to take unit time, our algorithms run in time $O(n^{f™2}$ log $\textit{n}),$ where $\textit{f}$ is the number of facets of the polyhedron determining the polyhedral norm. Thus, for example, we have $O(n^{2}$ log $\textit{n})$ algorithms for the cases of points in the plane under the Rectilinear and Sup norms. This is in contrast to the fact that finding a $\textit{minimum}$ length tour in each case is NP-hard. Our approach can be extended to the more general case of $\textit{quasi-norms}$ with a not necessarily symmetric unit ball, where we get a complexity of $O(n^{2f™2}$ log $\textit{n}).For$ the special case of two-dimensional metrics with $\textit{f}$ = 4 (which includes the Rectilinear and Sup norms), we present a simple algorithm with $\textit{O}(\textit{n})$ running time. The algorithm does not use any indirect addressing, so its running time remains valid even in comparison based models in which sorting requires $Ω(\textit{n}$ log $\textit{n})$ time. The basic mechanism of the algorithm provides some intuition on why polyhedral norms allow fast algorithms.Complementing the results on simplicity for polyhedral norms, we prove that, for the case of Euclidean distances in $&##x211D;^{d}$ for $\textit{d}$ ≥ 3, the Maximum TSP is NP-hard. This sheds new light on the well-studied difficulties of Euclidean distances.
ISSN 00045411
Age Range 18 to 22 years ♦ above 22 year
Educational Use Research
Education Level UG and PG
Learning Resource Type Article
Publisher Date 2003-09-01
Publisher Place New York
e-ISSN 1557735X
Journal Journal of the ACM (JACM)
Volume Number 50
Issue Number 5
Page Count 24
Starting Page 641
Ending Page 664

Open content in new tab

   Open content in new tab
Source: ACM Digital Library