Dr. Volker Kaibel

Vorlesung Approximationsalgorithmen in der
Kombinatorischen Optimierung
4 St. Mo., Mi. 13-15 im Hörsaal Pohligstr. 1,

Übungen zur Vorlesung Approximationsalgorithmen in der Kombinatorischen Optimierung
Fr. 9-11 Uhr


Wie die Komplexitätstheorie lehrt, ist es für viele der interessantesten (und praxisrelevantesten) kombinatorischen Optimierungsprobleme vorraussichtlich unmöglich, effiziente Algorithmen zu finden. Die Vorlesung handelt von effizienten Algorithmen, die fü r solche Probleme im allgemeinen zwar keine optimalen Lösungen berechnen, aber doch solche, für die man a priori eine gewisse Gütegarantie geben kann. Die Theorie solcher Approximationsalgorithmen ist in den 90er Jahren vehement vorangetrieben worden. Das PCP-Theorem lieferte völlig neue Möglichkeiten, für einzelne Probleme ihre jeweiligen Grenzen der Approximierbarkeit aufzuzeigen, randomisiertes Runden und semidefinite Programmierung führten nicht nur zu spektakulären neuen Approximationsalgorithmen für d as Problem des maximalen Schnittes in einem Graphen, sondern in der Folge auch zu Verfahren für eine Reihe von anderen Probleme, und mit dem Nachweis, daß das Problem des Handlungsreisenden für in der euklidischen Ebene liegende Städte beliebig gut zu appr oximieren ist, wurde eine seit Mitte der 70er Jahre offene und weithin beachtete Frage gelöst. Die Vorlesung soll sowohl diese sehr jungen Höhepunkte der Forschung in der Kombinatorischen Optimierung als auch klassische Approximationsresultate vermitteln, wobei diverse algorithmische Prinzipien und Ansätze vorgestellt werden. Sie wendet sich an Studierende im Hauptstudium, welche die Vorlesungen Informatik I und II gehört haben, und eignet sich sehr gut als Ergänzung zu den Vorlesungen Optimierungsalgorithm en I/II und Komplexitätstheorie, baut auf diesen jedoch nicht auf. Sowohl Studierende der Wirtschaftsinformatik als auch Studierende mit Nebenfach Informatik können sich bei Herrn Prof. Jünger über den Stoff der Vorlesung im Rahmen von Diplomprüfungen prü fen lassen. Als Einführung in das Gebiet empfehle ich das Buch Approximation Algorithms for NP-Hard Problems, Dorit S. Hochbaum (ed.), PWS Publishing Company, Boston, 1997.


Neben Vertiefung und Ergänzung des Stoffes der Vorlesung sollen die Übungen auch dazu dienen, einige der vorgestellten Algorithmen zu implementieren und praktisch zu testen.