Das Seminar fand statt an drei Tagen, nämlich am 24.02., 17.03. und 18.03. 2003.
Reihenfolge der Vorträge:
24. Februar: 1 Scheduling (2 Vortragende), 2 TSP, 3 Primal-Dual (2 Vortr.)
17. März : 1 Set Cover, 2 Bin Packing
3 Shortest Superstring
18. März : 1 Steiner, 2 Multiway, 3 3-färbbare Graphen
Liste der Vortragenden
| Scheduling I und II | Lena Wiese, Ivana Vukusic |
| Bin Packing | Daniel Blum |
| Shortest Superstring | Simon Muras |
| Set Cover | Daniel Becker |
| Euklidisches TSP | Michael Simeonescu |
| Steinerbaum | Irina Alesker |
| Multiway Cut | Stefan Tannenbaum |
| Färben von 3färbbaren Graphen | Ingo Roderfeld |
| Primal/Dual-Methode | Dino Hasanbegovic, Quang Bao Anh Bui |
Worum geht es im Seminar?
Für eine Reihe von wichtigen Optimierungsproblemen
sind keine Polynomialzeitalgorithmen bekannt.
Dann bieten sich Algorithmen an, die zwar nicht das Optimum
finden, aber Lösungen, die dicht am Optimum liegen,
so genannte Approximationsalgorithmen.
Um diese soll es in diesem Seminar gehen, das
sich an Studierende im Hauptstudium wendet.
Grundlage sind die Bücher "Approximation Algorithms" von V.V. Vazirani und "Approximation Algorithms for NP-hard Problems" von D.S. Hochbaum.