Planar Euclidean Maximum TSP

What is the complexity of finding a tour of maximum Euclidean length for a planar point set?

Abstract

Determine the computational complexity of finding a maximum-length traveling-salesperson tour through points in the Euclidean plane.

Background and progress

A polynomial-time approximation scheme is known [Barvinok, 1996]. The problem is polynomial for polyhedral metrics, while the Euclidean problem is NP-hard in three dimensions [Fekete, 1999]; the planar Euclidean case remains open. The original problem appears in the Open Problems Project at https://topp.openproblem.net/p49.

Reference papers

Two algorithmic results for the traveling salesman problemAlexander BarvinokMathematics of Operations Research · 1996
Simplicity and hardness of the maximum traveling salesman problem under geometric distancesSándor P. FeketeProceedings of the 10th Annual ACM-SIAM Symposium on Discrete Algorithms · 1999

Planar Euclidean Maximum TSP

Coming soon

Organizer