Maximum Traveling Salesman Problem

Title: Maximum Traveling Salesman Problem

Research Question: How can we efficiently find the longest possible path through a set of points in a geometric space, given different distance norms?

Methodology: The researchers considered two classes of norms: polyhedral norms and geometric norms. Polyhedral norms are determined by a centrally-symmetric polyhedron that defines the unit ball, while geometric norms include Euclidean and Lp norms. They proposed algorithms to solve the Maximum Traveling Salesman Problem (MTSP) for both classes.

Results: For polyhedral norms, they showed that the problem can be solved in polynomial time. They presented a simple algorithm with O(n) running time for 2-dimensional metrics, which does not require indirect addressing and remains effective even in comparison-based models. For geometric norms, they proved that the MTSP is NP-hard for Euclidean distances in Rd for d ≥ 3, shedding new light on the difficulties of Euclidean distances.

Implications: The results suggest that polyhedral norms allow for faster algorithms to solve the MTSP, while the hardness of the problem for geometric norms, particularly Euclidean distances, highlights the complexity of this problem. The simple algorithm for 2-dimensional metrics without indirect addressing provides an intuitive understanding of why polyhedral norms enable fast algorithms.

Link to Article: https://arxiv.org/abs/0204024v1 Authors: arXiv ID: 0204024v1