Wintersemester 2025/26
Thema: Approximationsalgorithmen für das Rundreiseproblem
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) | Luise Puhlmann |
| 4 | 17.11. | 1.12. | Jens Reetmeyer | Removable Pairings (Sections 12.1 bis 12.3 und 12.6) | Susanne Armbruster |
| 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 |
- Alle Teilnehmerinnen und Teilnehmer müssen die Seite 1-28 des Buches vor dem Seminar gelesen haben.
- Von allen Teilnehmerinnen und Teilnehmern werden eine regelmäßige Teilnahme und eine aktive Mitarbeit erwartet.
- Die Vorträge sollen höchstens 75 Minuten dauern. Anschließend sind dann 15 Minuten für eine Diskussion vorgesehen.
- Alle Teilnehmerinnen und Teilnehmer müssen eine Zusammenfassung ihres Vortrags anfertigen, die mindestens eine und höchstens zwei Seiten lang ist.
- Alle Teilnehmerinnen und Teilnehmer müssen außerdem einen Probevortrag halten, der zwei bis drei Wochen vor dem eigentlichen Vortrag stattfindet. Ein erfolgreicher Probevortrag ist Voraussetzung für den Vortrag im Seminar.
Die Dozentinnen und Dozenten der Diskreten Mathematik