The geometric maximum travelling salesman problem

A. Barvinok, Sandor Fekete, D.S. Johnson, T. Tamir, Gerhard Woeginger, Russ Woodroofe

Research output: Contribution to journalArticleAcademicpeer-review

34 Citations (Scopus)

Abstract

We consider the traveling salesman problem when the cities are points in ℝd for some fixed 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 maximum length can be solved in polynomial time. If arithmetic operations are assumed to take unit time, our algorithms run in time O(nf−2 log n), where f is the number of facets of the polyhedron determining the polyhedral norm. Thus, for example, we have O(n2 log 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 minimum length tour in each case is NP-hard. Our approach can be extended to the more general case of quasi-norms with a not necessarily symmetric unit ball, where we get a complexity of O(n2f−2 log n).For the special case of two-dimensional metrics with f = 4 (which includes the Rectilinear and Sup norms), we present a simple algorithm with O(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 Ω(n log 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 ℝd for d ≥ 3, the Maximum TSP is NP-hard. This sheds new light on the well-studied difficulties of Euclidean distances.
Original languageEnglish
Pages (from-to)641-664
Number of pages24
JournalJournal of the Association for Computing Machinery
Volume50
Issue number5
DOIs
Publication statusPublished - 2003

Keywords

  • METIS-213309

Fingerprint Dive into the research topics of 'The geometric maximum travelling salesman problem'. Together they form a unique fingerprint.

  • Cite this

    Barvinok, A., Fekete, S., Johnson, D. S., Tamir, T., Woeginger, G., & Woodroofe, R. (2003). The geometric maximum travelling salesman problem. Journal of the Association for Computing Machinery, 50(5), 641-664. https://doi.org/10.1145/876638.876640