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, considering different distance norms?

Methodology: The researchers considered two classes of distance norms: polyhedral norms and geometric norms. They proposed algorithms to solve the Maximum Traveling Salesman Problem (MTSP) for each class.

Results:

1. For polyhedral norms, they showed that the problem can be solved in polynomial time. They provided an O(nf−2logn) algorithm, which is particularly efficient for norms with a small number of facets.

2. For the special case of two-dimensional metrics with four facets (which includes the Rectilinear and Sup norms), they presented a simple algorithm with O(n) running time. This algorithm does not require indirect addressing, making it efficient even in comparison-based models.

3. They also proved that for the case of Euclidean distances in three-dimensional or higher spaces, the MTSP is NP-hard.

Implications: These results provide insights into the complexity of the MTSP for different distance norms. The efficient algorithms for polyhedral norms open up possibilities for solving practical problems in areas such as logistics, routing, and network optimization. The NP-hardness result for Euclidean distances highlights the challenges in solving such problems in higher dimensions.

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