Research Institute for Discrete Mathematics

Module "Advanced Topics in Discrete Mathematics (V5C1)"

Approximation Algorithms for the Traveling Salesman Problem

Winter Term 2023/24

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