Graduate Seminar on Discrete Optimization (S4C1)

Summer 2021

Randomized Algorithm with Approximation Ratio Better than 3/2 for Symmetric TSP

In 2020, Anna Karlin, Nathan Klein, and Shayan Oveis Gharan published the first proof of an approximation ratio better than 3/2 for Symmetric TSP. Their randomized algorithm is the first to beat the classical 3/2-approximation algorithm by Christofides and Serdjukov. It samples a random spanning tree according to a maximum entropy distribution with marginals corresponding to the subtour LP solution, and then proceeds with parity correction like Christofides. The analysis is complicated, and the entire seminar is devoted to the proof that the expected cost of parity correction is less than r times the optimum cost of a tour, where r is a constant strictly smaller than 1/2. The paper can be found here:

Class hours: Mondays 14:15-15:45. Approval talks: 16:15-17:45

Number Approval Talk Talk Name Topic Mentoring
1 12.4. 26.4. Alexandra Niemann Maximum entropy distributions of spanning trees Siad Daboul
2 19.4. 3.5. Antonia Ellerbrock Strongly Raleigh measures and random spanning trees Stefan Rabenstein
3 26.4. 10.5. Marena Richter Main theorem - Structure of the proof Pietro Saccardi
4 3.5. 17.5. Fabien Nießen Cuts crossed on both sides and polygons Pietro Saccardi
5 10.5. 31.5. Felix Horchler Cuts crossed on one side and hierarchy of cuts Benjamin Rockel
6 17.5. 7.6. Lukas Gehring Gurvits Lemma Benjamin Rockel
7 31.5. 14.6. Daphne Rohrßen Good edges Stefan Rabenstein
8 7.6. 21.6. Sebastian Lüderssen Matching Meike Neuwohner
9 14.6. 28.6. Eva Gebertz Reduction and payment: good top edges Tilmann Bihler
10 21.6. 5.7. Martin Drees Reduction and payment: increase for bottom edges Tilmann Bihler
11 28.6. 12.7. Lotte Blank Reducing Path TSP to TSP (I) Niklas Schlomberg
12 5.7. 19.7. Malte Schürks Reducing Path TSP to TSP (II) Meike Neuwohner

A list of talks with a more detailed description of the topics can be found here.

Prof. Dr. B. Korte,
Prof. Dr. J. Vygen,
Prof. Dr. S. Hougardy,
Prof. Dr. S. Held,
Dr. U. Brenner