Approximation Algorithms for the Asymmetric Traveling Salesman Problem

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

• Asadpour, A., Goemans, M.X., Mądry, A., Oveis Gharan, S., and Saberi, A.: An O(log n/log log n)-approximation algorithm for the asymmetric traveling salesman problem. Operations Research 65 (2017), 1043-1061
• Svensson, O.: Approximating ATSP by relaxing connectivity. Proceedings of the 56th Annual IEEE Symposium on Foundations of Computer Science (FOCS 2015), 1-19
• Svensson, O., Tarnawski, J., and Végh, L.: A constant-factor approximation algorithm for the asymmetric traveling salesman problem. Journal of the ACM 67 (2020), Article 37
• Traub, V., and Vygen, J.: An improved approximation algorithm for ATSP. SIAM Journal on Computing, to appear. Preliminary version in the Proceedings of the 52nd Annual ACM Symposium on the Theory of Computing (STOC 2020), 1-13
• Feige, U., and Singh, M.: Improved approximation algorithms for traveling salesperson tours and paths in directed graphs. Proceedings of the 10th International Workshop on Approximation Algorithms for Combinatorial Optimization Problems; LNCS 4627 (M. Charikar, K. Jansen, O. Reingold, J.D.P. Rolim, eds.), Springer, Berlin 2007, pp. 104-118
• Köhne, A., Traub, V., and Vygen, J.: The asymmetric traveling salesman path LP has constant integrality ratio. Mathematical Programming 183 (2020), 379-395
• Traub, V.: Approximation Algorithms for Traveling Salesman Problems. PhD thesis, University of Bonn 2020

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.