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.
This course will be in English. An introduction to the subject can be found in this survey paper from 2012. However, this covers only a small part of the course; I will try 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) | |
| Class Hours: | Tuesdays and Thursdays 16:15-17:45 |
| Room: | Seminarraum, Lennéstr. 2 |
| Exams: | Oral exams, scheduled individually. Tentative dates: August 15 and September 26. |
Professor J. Vygen