Das Rundreiseproblem (Traveling Salesman Problem, TSP) ist wohl das berühmteste kombinatorische Optimierungsproblem. Der Entwurf und die Analyse immer besserer Approximationsalgorithmen hat sich als sehr fruchtbar erwiesen. In diesem Seminar besprechen wir die Grundlagen und einige dieser Algorithmen. Es basiert auf Teilen des neuen Buchs: V. Traub, J. Vygen: Approximation Algorithms for Traveling Salesman Problems, Cambridge University Press 2025.
| Nr. | Probevortrag 16 Uhr c.t. |
Vortrag 14 Uhr c.t. |
Name | Thema | Betreuung |
|---|---|---|---|---|---|
| 1 | 20.10. | 10.11. | Paul Jakob Schmidt | Wolsey’s Theorem (Sections 2.3 und 2.4) | Martin Drees |
| 2 | 27.10. | 17.11. | Benjamin Onsa | Splitting Off (Sections 2.5 bis 3.2) | Paula Heinz |
| 3 | 10.11. | 24.11. | Jakob von Rosen | ATSP Integrality Ratio (Sections 3.5 und 3.6) | Susanne Armbruster |
| 4 | 17.11. | 1.12. | Jens Reetmeyer | Removable Pairings (Sections 12.1 bis 12.3 und 12.6) | Luise Puhlmann |
| 5 | 24.11. | 8.12. | Julian Kemp | 13/9-Approximation for Graph TSP (Sections 12.4 und 12.5) | Daniel Ebert |
| 6 | 1.12. | 15.12. | Annette Breitbach | Ear-Decompositions (Sections 13.1 bis 13.3 bis Seite 286) | Antonia Ellerbrock |
| 7 | 8.12. | 22.12. | Henning Micheel | Frank’s Theorem and Nice Ear-Decompositions (Section 13.3 und 13.4, Seiten 287 bis 292) | Edgar Perner |
| 8 | 15.12. | 12.1.2026 | Alexander Rohe | 7/5-Approximation for Graph TSP (Sections 13.4 und 13.5, Seiten 292 bis 299) | Daniel Blankenburg |
| 9 | 22.12. | 19.1. | Hongkunyun Song | Path TSP (Sections 14.1 und 14.2) | Armin Settels |
| 10 | 12.1.2026 | 26.1. | Jonah Böll | Gao’s Theorem (Sections 14.3 bis 14.5) | Lorenzo Conti |