Approximation Algorithms for Graph TSP and Asymmetric TSP

The traveling salesman problem (TSP) is probably the most famous combinatorial optimization problem. Recently, the study of approximation algorithms has made significant progress. We discuss two of these results in detail. First, we present the best known approximation algorithm for Graph TSP, with ratio 7/5. Second, we present the best known approximation algorithm for Asymmetric TSP, with ratio 17+ε. Further related results will be discussed as well.

This course will be in English and largely based on the new book that we published earlier this year.

Prerequisites:	Combinatorial Optimization (in particular basic knowledge on graphs, linear programming, network flows, NP-completeness, and approximation algorithms. Please read and understand pages 1–28 of the book in advance.
Class Hours:	Tuesdays and Thursdays 16:15-18:00
Room:	Seminarraum, Lennéstr. 2
Exams:	Oral exams, to be scheduled individually.