next up previous
Next: Problem 50: Pointed Spanning Up: The Open Problems Project Previous: Problem 48: Bounded-Degree Minimum


Problem 49: Planar Euclidean Maximum TSP

Statement
What is the complexity of finding a tour of maximum Euclidean length for a planar point set?
Origin
[Bar96] showed that there is a PTAS for the problem. No earlier mention is known.
Status/Conjectures
Open.
Motivation
How does the complexity of a natural problem depend on the geometry of distances?
Partial and Related Results
[BJrW98] showed that a maximum length tour can be found in polynomial time for polyhedral metrics in spaces of finite dimension, i.e., for metrics for which the unit ball is a convex body with f facets. The resulting complexity is O(nf-2log n).

[Fek99] showed that the maximum TSP can be solved in time O(n) for rectilinear distances in the plane, but is NP-hard for Euclidean distances in three-dimensional space, or on the surface of a sphere. Conjectures the case of planar Euclidean distances to be NP-hard.

More recent details and related problems can be found in [BFJ+03].

Related Open Problems
The problem is not even known to be in NP. A polynomial algorithm would require some understanding of problem 33 (sum of square roots), at least for classes of instances arising from the computation of tour length.

Also related is the Planar Euclidean maximum scatter TSP: What is the complexity of finding a tour for a planar point set in ℜd, such that the Euclidean length of the shortest edge is maximized? Stated in [ACM+97], shown NP-hard in dimensions d≥3 in [Fek99], open for d = 2. Also, no bounds on approximation are known in a geometric context; the best known aproximation algorithm from [ACM+97] achieves an approximation factor of 2, but does not use geometry.

Appearances
[Fek98], [BFJ+03]
Categories
traveling salesman; optimization; point sets
Entry Revision History
S.P. Fekete, 1 Aug. 2003.

Bibliography

ACM+97
Esther M. Arkin, Y.-J. Chiang, Joseph S. B. Mitchell, Steven S. Skiena, and T. Yang.
On the maximum scatter TSP.
In Proc. 8th ACM-SIAM Sympos. Discrete Algorithms, pages 211-220, 1997.

BFJ+03
A. Barvinok, S. P. Fekete, D. S. Johnson, A. Tamir, G. J. Woeginger, and R. Wodroofe.
The geometric maximum Traveling Salesman problem.
Journal of the ACM, 50:641-664, 2003.

Bar96
Alexander I. Barvinok.
Two algorithmic results for the TSP.
Math. Oper. Res., 21:65-84, 1996.

BJrW98
Alexander Barvinok, David S. Johnson, Gerhard J. Woeginge r, and Russell Woodroofe.
The maximum traveling salesman problem under polyhedral norms.
In Sixth Conference on Integer Programming and Combinatorial Optim ization, volume 1412 of Springer LNCS, pages 195-201, June 1998.

Fek98
Sándor P. Fekete.
Simplicity and hardness of the maximum traveling salesman problem under geometric distances.
Manuscript (submitted), Mathematisches Institut, Universität zu Köln, 1998.

Fek99
S. P. Fekete.
Simplicity and hardness of the maximum traveling salesman probl em under geometric distances.
In Proc. 10th ACM-SIAM Sympos. Discrete Algorithms, pages 337-345, 1999.


next up previous
Next: Problem 50: Pointed Spanning Up: The Open Problems Project Previous: Problem 48: Bounded-Degree Minimum
The Open Problems Project - December 04, 2015