The traveling salesman problem (TSP) is probably the most famous combinatorial optimization problem. It is easy to understand but notoriously hard. Since the 1950s, it played a key role in combinatorial optimization: many new techniques were first developed for the TSP and later applied to many other problems. Since 1976, the best known approximation ratio for the metric TSP is 3/2, by Christofides. This also gives an upper bound on the integrality ratio of the subtour relaxation, as shown by Wolsey in 1980. Since then, many researchers tried (in vain) to improve these upper bounds. The true value of the integrality ratio is conjectured to be 4/3 (this ratio is attained by instances of the so-called graph TSP). After a long period of almost no progress, there has been a rapid development since 2010, and this is the subject of this course. For the asymmetric TSP, the graph TSP, the s-t-path TSP (where start and end of the tour do not coincide), and related problems, the ratios have been improved recently, and many new techniques have been introduced to obtain these results. We try to cover most of them, except for the constant-factor approximation algorithm for the asymmetric TSP, which was the subject of a separate course in the previous semester.
This course will be taught in English, jointly with Vera Traub. There will be no formal exercises. An introduction to the subject can be found in this survey paper from 2012. However, this covers only a small part of the course; we will extend this text during the course.
| Prerequisites: | Combinatorial Optimization, Approximation Algorithms |
| (in particular basic knowledge on graphs, linear programming, network flows, matroids, matching, T-joins, NP-completeness, and approximation algorithms; see, e.g., Chapters 1-16 of the Korte-Vygen textbook). | |
| This course is independent of the ATSP course in the previous semester. | |
| Class Hours: | Tuesdays and Thursdays 16:15-17:45 |
| Room: | Seminarraum, Lennéstr. 2 |
| Exams: | Oral exams, scheduled individually. |
Professor J. Vygen