idw – Informationsdienst Wissenschaft
Nachrichten, Termine, Experten
Nachrichten, Termine, Experten
PhD student Vera Traub and her supervisor, Jens Vygen, professor at the Research Institute for Discrete Mathematics in Bonn, received a Best Paper Award at the world’s leading Symposium on Discrete Algorithms (SODA) in New Orleans. With their 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.
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
Honor (from left): Prof. Dr. Jens Vygen, Prof. Dr. Artur Czumaj (Program Committee Chair of SODA 201 ...
(c) Photo: Takao Asano
None
Criteria of this press release:
Journalists, all interested persons
Mathematics
transregional, national
Personnel announcements
English
Honor (from left): Prof. Dr. Jens Vygen, Prof. Dr. Artur Czumaj (Program Committee Chair of SODA 201 ...
(c) Photo: Takao Asano
None
You can combine search terms with and, or and/or not, e.g. Philo not logy.
You can use brackets to separate combinations from each other, e.g. (Philo not logy) or (Psycho and logy).
Coherent groups of words will be located as complete phrases if you put them into quotation marks, e.g. “Federal Republic of Germany”.
You can also use the advanced search without entering search terms. It will then follow the criteria you have selected (e.g. country or subject area).
If you have not selected any criteria in a given category, the entire category will be searched (e.g. all subject areas or all countries).
