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.
The work was honored on January 8th, 2018 with the "Best Paper Award" of the ACM-SIAM Symposium on Discrete Algorithms (SODA). SODA is the world's leading conference on discrete algorithms. 180 of the 547 works submitted were accepted this year, and only two of them received the "Best Paper Award".
Excellent research
The main focus of the Research Institute for Discrete Mathematics lies in the field of discrete mathematics and its applications, especially in combinatorial optimization and chip design. The Research Institute for Discrete Mathematics is an institute of the Hausdorff Center for Mathematics (HCM), a Cluster of Excellence at the University of Bonn. Here, German and international scientists are investigating numerous topics of mathematics and mathematical economics.
Contact for the media:
Stefan Hartmann
Public Relations and Events
Hausdorff Center for Mathematics
University of Bonn
Phone: 0228/733138
Email: stefan.hartmann@hcm.uni-bonn.de