Forschungsinstitut für Diskrete Mathematik

Seminar Diskrete Optimierung

Sommersemester 2003

Thema: Approximationsalgorithmen

Für NP-harte Optimierungsprobleme läßt sich, wenn nicht P=NP gilt, kein effizienter (d.h. polynomieller) Algorithmus angeben, der beweisbar stets eine Optimallösung findet. Daher drängt sich für diese Probleme die Frage nach effizienten Algorithmen auf, für die man wenigstens eine obere Schranke für die Abweichung zwischen dem Wert ihrer Ausgabe und dem Wert einer Optimallösung garantieren kann. In den vergangenen Jahren konnten für viele harte Probleme solche Approximationsalgorithmen gefunden werden. In einigen Fällen ließen sich sogar Approximationsschemata angeben, mit deren Hilfe sich eine Optimallösung beliebig gut approximieren läßt.
In dem Seminar sollen anhand einiger interessanter Probleme neuere Ideen für Approximationsmethoden vorgestellt und analysiert werden.
Grundlage der Vorträge sind Kapitel des Buches Approximation Algorithms von Vijay V. Vazirani (Springer-Verlag 2001, ISBN 3-540-65367-8) sowie Originalarbeiten.
Termin: mittwochs 16-18 im Seminarraum des Instituts
Nr. Datum Name Thema Betreuung
1 30. 4. Fabio Hake Kapitel 4,
Goldschmidt and Hochbaum: Polynomial Algorithm for the k-Cut Problem.
Jürgen Werber
2 7. 5. Friedrich Regen Kapitel 5,
Hochbaum and Shmoys: A Unified Approach to Approximation Algorithms for Bottleneck Problems.
Jens Maßberg
3 14. 5. Minglai Cai Kapitel 6,
Even, Naor, Schieber and Sudan: Approximating Minimum Feedback Sets and Multi-Cuts in Directed Graphs.
Ulrich Brenner
4 21. 5. Florian Berger Kapitel 7,
Armen and Stein: A 2 2/3- Approximation Algorithm for the Shortest Superstring Problem.
Stephan Held
5 28. 5. Peter Hahnen Kapitel 9,
Kapitel 10,
Coffman and Lueker: Approximation Algorithms for Extensible Bin Packing.
Jens Maßberg
6 18. 6. Markus Griem Gröpl, Hougardy, Nierhoff and Prömel: Approximation Algorithms for the Steiner Tree Problems in Graphs.
Sven Peyer
7 25. 6. Ilya Achkinazi Kapitel 17,
Lenstra, Shmoys and Tardos: Approximation Algorithms for Scheduling Unrelated Parallel Machines
Matthias Müller-Hannemann
8 2. 7. Robert Spindler Kapitel 18,
Garg, Vazirani, Yannakakis : Primal-Dual Approximation Algorithms for Integral Flow and Multicut in Trees. 		Dirk Müller
9 16. 7. Henning Lemster Kapitel 19,
Kapitel 20 		Ulrich Brenner
10 23. 7. Roman Scherzer Kapitel 21 Jürgen Werber

Scheinkriterien:

erfolgreicher Seminarvortrag, regelmäßige Teilnahme an den Veranstaltungen und aktive Mitarbeit
Prof. Dr. B. Korte
Dr. M. Müller-Hannemann
Dr. J. Vygen