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: https://arxiv.org/abs/2007.01409
| 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.