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:

- 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. |