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(n^f-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 $\Re^{d}_{}$, such that the Euclidean length of the shortest edge is maximized? Stated in [ACM+97], shown NP-hard in dimensions d $\geq$ 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.