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 MitarbeitProf. Dr. B. Korte
Dr. M. Müller-Hannemann
Dr. J. Vygen