Gegenstand dieser zweistündigen Spezialvorlesung ist das bekannte Rundreiseproblem, besser bekannt unter dem englischen Namen Traveling-Salesman-Problem. Es diente in den vergangenen 50 Jahren in vielerlei Hinsicht als das Problem, für das völlig neue Methoden der Diskreten Optimierung entwickelt wurden, die dann auch bei ganz anderen Problemen zum Einsatz kamen. Ein genaues Studium des Traveling-Salesman-Problems beinhaltet daher ein vielseitiges Themenspektrum wie Komplexität und Approximationsalgorithmen, LP-Relaxierungen und polyedrische Kombinatorik, Branch-and-Cut-Verfahren und Lokale Suche. Auch in jüngster Zeit gab es noch beachtliche Fortschritte, von denen wir einige in der Vorlesung kennenlernen werden.
Als Einführung und Überblick mag dienen Kapitel 21 des Buches Combinatorial Optimization: Theory and Algorithms (B. Korte, J. Vygen), Algorithms and Combinatorics 21, Springer-Verlag, 2. Auflage 2002, sowie die dort zitierte Literatur. Die Vorlesung wird jedoch vielfach über den in diesem Kapitel enthaltenen Stoff hinausgehen.
| Vorkenntnisse: | Grundstudium; Vorkenntnisse aus dem Vorlesungszyklus ``Diskrete Mathematik'' sind hilfreich. |
| Ort: | Gerhard-Konow-Hörsaal (Lennéstr. 2) |
| Zeit: | Dienstags 12-14 Uhr |
| Beginn: | 15.10.2002 |
J. Vygen