The traveling salesman problem (TSP) is the probably 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 other problems. After a long period of almost no progress, there has been a rapid development since 2010 and many new techniques have been introduced. These recent developments are the subject of this course.
Basic knowledge in combinatorial algorithms, in particular graphs, network flows, and linear programming, is required.
| Class hours: | Tuesdays and Thursdays 4-6 pm (16:15-17:45) |
| First lecture: | October 10, 2023 |
| Room: | Seminar room (in the Arithmeum building, Lennéstr. 2) |
| eCampus: | see here |
| Exams: | oral exams |
Prof. Dr. V. Traub