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.

• Folien aus der Vorbesprechung
• Anmerkungen zu Seminarvorträgen
• Link zum Buch

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.