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 should also have the time to discuss some consequences and variants. This course will be in English.

No. Date Syllabus (Q+A sessions not shown)
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
12 Nov 25 Analyzing Svensson's algorithm for Graph ATSP
13 Nov 30 Strongly laminar instances and vertebrate pairs
14 Dec 2 Reducing ATSP to vertebrate pairs
15 Dec 7 Reducing vertebrate pairs to subtour cover
16 Dec 9 Svensson's algorithm for vertebrate pairs
17 Dec 14 Split graph, witness flows
18 Dec 16 Rerouting, rounding
19 Dec 21 Finishing the simple subtour cover algorithm
20 Jan 11 Acyclic witness flows
21 Jan 13 Completing the ATSP algorithm, Asymmetric Path TSP
22 Jan 18 Feige-Singh reduction, Asymmetric Path TSP LP
23 Jan 20 Reducing Path TSP to strongly laminar instances
24 Jan 25 Black-box reduction for integrality ratio and the graph case
25 Jan 27 New approximation algorithm for Asymmetric Path TSP
26 Feb 1 Outlook, summary

Works that we will discuss in detail include: We will also discuss new unpublished work by Vera Traub and myself.

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 scheduled individually on February 14 and March 21.

Professor J. Vygen