Closer to the optimal tour

With a newly developed algorithm, tours along any number of cities can be determined that come "as close as possible" to the shortest tour.

The "traveling salesman problem" is world-famous and was formulated for the first time in the year 1930: Given are a starting point, an end point and a set of other points, which are to be visited in between. The goal is to find the shortest tour by optimizing the order. Applications can be found in logistics or tour planning: For example, the question may arise how to travel from Kiel to Munich on the shortest tour if you want to visit all the other 14 capitals of the federal states of Germany along the way. For very few points you can enumerate all possible orders, but regarding the tour along the federal state capitals, for instance, there are over 80 billion theoretical options.

An NP-hard problem

The problem of finding the best order for such a tour is classified as particularly hard. Problems that can be solved "relatively fast" with algorithms (in so-called polynomial time) belong to class P. Problems whose given solutions can be verified "relatively fast" belong to the class NP. To this day one does not know whether one can solve problems of the class NP "relatively fast", this means if P = NP holds. This so-called "P versus NP problem" is one of the seven Millennium Prize Problems selected by the Clay Mathematics Institute. In the class NP, there are certain distinguished problems that are particularly difficult to solve. All other problems of the class NP can be reduced to these problems. Problems that are at least as hard to solve as these distinguished problems are referred to as "NP-hard". The "traveling salesman problem" is such an "NP-hard" problem.

A new algorithm

For the special case where the starting and the end point of the tour are identical, the Cypriot mathematician Nicos Christofides found an effective algorithm already in 1976. The resulting tour is at most half the length longer than the optimal tour. This quality guarantee of the determined tour constitutes a kind of natural threshold. To reach this threshold with different starting and end points has turned out to be much more difficult. With a new "recursive dynamic programming" approach, Vera Traub and Jens Vygen were now able to come as close to this threshold as possible: Tours determined with the new algorithm are at most x times as long as the optimal tour, where x is arbitrarily close to 1.5. The new algorithm might also be used in other optimization problems in the future.

Publication:

Vera Traub, Jens Vygen: Approaching 3/2 for the s-t-path TSP. Submitted. Preliminary version in the Proceedings of the 29th Annual ACM-SIAM Symposium on Discrete Algorithms (2018), 1854-1864 (Best Paper Award)

 

The authors were awarded the Best Paper Award at the world’s leading Symposium on Discrete Algorithms (SODA) in New Orleans for their paper. (see press release of January 9, 2018)