The traveling salesman problem (TSP) is probably the most famous combinatorial optimization problem. It is easy to understand but notoriously hard. In the asymmetric version, we are given a finite set of cities and nonnegative distances and ask for a shortest tour that visits every city at least once. No constant-factor approximation algorithm for this problem was known until the recent work of Svensson, Tarnawski and Végh (STOC 2018). In this course, we present their algorithm in detail, with full proofs. We might also have the time to discuss some consequences and variants.
This course will be in English. There will be no formal exercises. For the following winter semester, I plan a course on the symmetric TSP.
| Prerequisites: | Combinatorial Optimization (in particular basic knowledge on graphs, linear programming, network flows, NP-completeness, and approximation algorithms; see, e.g., Chapters 1-16 of the Korte-Vygen textbook) |
| Class Hours: | Tuesdays 16:15 - 18:00 |
| Room: | Seminarraum, Lennéstr. 2 |
| Exams: | Oral exams on July 19 and September 30, scheduled individually. |
Professor J. Vygen