Generalizations of the Traveling Salesman Problem

The traveling salesman problem (TSP) is probably the most famous combinatorial optimization problem. Recently, the study of approximation algorithms has made significant progress. In this course, we will study generalizations, including (Symmetric and Asymmetric) Path TSP, Vehicle Routing, Prize-Collecting TSP, A Priori TSP, and Orienteering. We will devise black-box reductions to the TSP and study the best known approximation algorithms, discovered only in the past few years.

This course will be in English and largely based on a new book that we are publishing this year. We will use some results from the previous TSP course by Vera Traub, but students who have not attended this course are also welcome.

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 and Thursdays 16:15-18:00
Room:	Seminarraum, Lennéstr. 2
Exams:	Oral exams, to be scheduled individually. Tentative dates: August 2 and September 16.