Forschungsinstitut für Diskrete Mathematik
Hauptseminar Diskrete Optimierung
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.
Wenn Sie an dem Seminar teilnehmen möchten, melden Sie sich bitte bis spätestens
Montag, 21.7, 9:00 Uhr (näheres in den Folien aus der Vorbesprechung oben).
-
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