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.
Vorbesprechung:
Dienstag, den 15. Juli 2025, um 18 Uhr s.t.
im Hörsaal, Lennéstr. 2
Studentinnen und Studenten, die Interesse an einer Seminarteilnahme haben,
aber nicht an der Vorbesprechung zu dieser Veranstaltung teilnehmen
können, werden gebeten, sich vorab mit
Ulrich Brenner,
brenner (at) or.uni-bonn.de,
Tel. 0228 / 73 87 49
in Verbindung zu setzen.
-
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