Research Institute for Discrete Mathematics

Module "Advanced Topics in Discrete Mathematics (V5C1)"

Lecture Course

Approximation Algorithms for the Asymmetric Traveling Salesman Problem

Winter term 2021/22

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. In a variant, the tour must begin at a given point and end at another given point. No constant-factor approximation algorithms for these problems were known until four years ago. In this course we review the classical algorithms and the very new ones with the best approximation guarantees, with complete proofs. A wide range of combinatorial optimization techniques will be used. We might also have the time to discuss some consequences and variants. This course will be in English.

No. Date Syllabus (preliminary)
1 Oct 12 Two equivalent ATSP versions, cycle cover algorithm
2 Oct 14 Two equivalent LP relaxations, splitting off
3 Oct 19 A third LP relaxation, integrality ratios
4 Oct 21 Lower bound on integrality ratio
5 Oct 26 Goemans-Carr-Vempala theorem, dual LP, uncrossing
6 Oct 28 Getting a laminar dual solution efficiently, sparse LP solutions
7 Nov 2 O(log n/log log n)-approximation via thin trees
8 Nov 4 Random spanning trees and electrical networks
9 Nov 16 Maximum entropy distribution, sampling spanning trees
10 Nov 18 Thin trees suffice, graph subtour covers
11 Nov 23 Re-initializing Svensson's algorithm for Graph ATSP

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 12:15-13:45 and Thursdays 16:15-18:00
Room: Seminarraum, Lennéstr. 2
Exams: Oral exams to be scheduled individually. Preliminary dates: February 14 and March 21.

Professor J. Vygen