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: 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.
- A regular participation in the talks and an active collaboration are mandatory for passing the seminar.
- The talks will take approximately 75 minutes. The remaining 15 minutes are intended for a discussion.
- Each participant has to write a summary consisting of one or two pages.
- Each participant has to give an approval talk (typically two or three weeks before the regular talk). Passing the approval talk is a prerequisite for giving the regular seminar talk.
Prof. Dr. B. Korte,
Prof. Dr. J. Vygen,
Prof. Dr. S. Hougardy,
Prof. Dr. S. Held,
Dr. U. Brenner