Closer to the optimal tour

Press release of the University of Bonn (slightly modified) of January 9, 2018

PhD student Vera Traub and her supervisor, Jens Vygen, a professor at the Research Institute for Discrete Mathematics in Bonn, received a Best Paper Award at the Symposium on Discrete Algorithms (SODA), one of the foremost conferences in its field, in New Orleans. With their newly developed algorithm, routes along any number of cities can be determined that come „as close as possible“ to the shortest route.

The “traveling salesman problem” is world-famous and was formulated for the first time in the year 1930: One is given 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 route by optimizing the order. Applications can be found in logistics or trip planning: For example, the question may arise how to travel in the fastest way from Kiel to Munich, visiting all the other 14 capitals of the federal states of Germany along the way. When the number of points is very low, one can enumerate all possible orders, but even the tour of state capitals mentioned above gives rise to over 80 billion options.

An NP-hard problem

The problem of finding the best order for such a tour is considered 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, no one knows whether one can solve problems of the class NP „relatively fast“, that is, whether 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 one such “NP-hard” problem.

A new algorithm

For the special case where the starting and the end point of the route are identical, the Cypriot mathematician Nicos Christofides found an effective algorithm in 1976. The resulting route is at most one and a half times as long as the optimal route. This guarantee of the route’s efficiency 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, scientists from Germany and abroad are investigating numerous topics in 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