Seminar: Approximationsschemata in Ablaufplanung, Graphentheorie und Geometrie
Sommersemester 2005
Allgemeines
- Teilnehmer: Die Zahl der Teilnehmer ist auf 12 begrenzt.
Inhalt
Wenn sich herausstellt, dass ein Problem NP-vollständig ist, ist ein Polynomialzeit-Approximationsschema das beste, worauf man hoffen kann: eine Schar von Algorithmen, die das entsprechende Optimierungsproblem beliebig gut annähern, wobei die Laufzeit jedes Algorithmus polynomiell in der Größe der Eingabe beschränkt sein muss.
Im Seminar sollen an Hand von Beispielproblemen aus der Ablaufplanung, der Graphentheorie und der algorithmischen Geometrie verschiedene Methoden behandelt werden, mit denen man Polynomialzeit-Approximationsschemata gewinnen kann. Darüber hinaus sollen Wege aufgezeigt werden, die zu Nichtapproximierbarkeitsresultaten führen.
Das Seminar ist besonders für Hörer im Hauptstudium mit Vorkenntnissen in der Graphen- und Komplexitätstheorie geeignet. Voraussetzung für die Teilnahme ist ein gutes Verständnis der ,,Groß-Oh''-Notation, d.h. man sollte wissen, was es bedeutet, dass eine Sequenz von n Zahlen in O(n log n) Zeit sortiert werden kann (und dass jedes Sortierverfahren, das auf Vergleichen beruht, Omega(n log n) Vergleiche benötigt).
Themen
| Teilnehmer | Thema | Vortragsfolien | Ausarbeitung | Referenz | Betreuer |
|---|---|---|---|---|---|
| Houssem Belloum | Das Traveling-Salesman-Problem | [pdf] | [pdf] | [3] Kap. 1-3 | Marc Benkert |
| Fabian Januszewski | Der TSP-Algorithmus von Rao & Smith | [pdf] | [3] Kap. 4, [4] | Marc Benkert | |
| Moritz Minzlaff | Approximationsschemata für andere geometrische Probleme | [3] Kap. 5-6 | Marc Benkert | ||
| Jürgen Graf | PTAS-Design durch Strukturierung der Eingabe | [pdf] | [pdf] | [2] Kap. 0.3 | Alexander Wolff |
| Herman Haverkort | PTAS-Design durch Strukturierung der Ausgabe | [pdf] | [2] Kap. 0.4 | Alexander Wolff | |
| N.N. | PTAS-Design durch Strukturierung der Ausführung | [2] Kap. 0.5 | Alexander Wolff | ||
| Nikolaus Mutsanas | Nichtapproximierbarkeitsresultate | [pdf] | [pdf] | [2] Kap. 0.6 | Étienne Schramm |
| Markus Völker | Geometrische aufspannende Bäume minimalen Durchmessers | [pdf] | [pdf] | [5] | Étienne Schramm |
| Daniel Bruns | Maximale unabhängige Mengen in planaren Graphen | [pdf] | [6] | Étienne Schramm |
Manche Referenzen können aus dem Netz heruntergeladen werden können. Gute Quellen dafür sind:
Gute Bücher über algorithmische Geometrie sind [7,8].
Termine
Das Seminar wird als Blockseminar an dem Wochenende 9.-11. Juli (Freitag abend bis Sonntag abend) in der Jugendfreizeit- und Bildungsstätte Baerenthal in den Vogesen durchgeführt. Deshalb ist die Zahl der Teilnehmer auf maximal 12 begrenzt. Die Kosten für Unterkunft und Vollverpflegung betragen 68 Euro pro Teilnehmer. Die Anfahrt wird nach Möglichkeit durch Fahrgemeinschaften in privaten PKWs organisiert.
Die ersten vier Treffen finden jeweils mittwochs 18:00-19:30 Uhr im SR 301 bzw. nach Vereinbarung statt.
| Datum | |
|---|---|
| 21.04. | Themenverteilung |
| 28.04. | Wie halte ich einen Seminarvortrag? |
| 05.05. | Kurzreferate (jeweils 5-10 Minuten) |
| 12.05. | Einführung in LaTeX für Folien, Zusammenfassung und Ausarbeitung |
| 26.05. | Abgabe der Zusammenfassung (cirka eine Seite) |
| 16.06. | Vorstellung der Vortragsfolien beim jeweiligen Betreuer |
| 09.-11.07. | Blockseminar in Baerenthal |
| 01.08. | Abgabe der Ausarbeitungen (cirka 5 Seiten) |
Literatur
- Frank Hoffmann and Christian Knauer. Wie gestalte ich einen Seminarvortrag? Freie Universität Berlin, 1998. [pdf]
- Petra Schuurman and Gerhard J. Woeginger. Approximation Schemes - A Tutorial. Technical Report Woe-65, TU Graz, 2001. [pdf]
- Sanjeev Arora. Approximation schemes for NP-hard geometric optimization problems: a survey. Mathematical Programming, 97(1-2):43-69, July 2003.
- Satish B. Rao and Warren D. Smith. Approximating geometrical graphs via „spanners“ and „banyans“. In Proc. 30th Annual ACM Symposium on Theory of Computing (STOC'98), pages 540-550, Dallas, TX, 1998.
- Michael J. Spriggs, J. Mark Keil, Sergei Bespamyatnikh, Michael Segal, and Jack Snoeyink. Computing a (1+eps)-Approximate Geometric Minimum-Diameter Spanning Tree. Algorithmica, 38(4):577-589, 2004.
- Brenda S. Baker. Approximation Algorithms for NP-Complete Problems on Planar Graphs. Journal of the ACM, 41(1):153-180, 1994.
- Mark de Berg, Marc van Kreveld, Mark Overmars, and Otfried Schwarzkopf. Computational Geometry: Algorithms and Applications. Springer-Verlag, Berlin, 1997.
- Rolf Klein. Algorithmische Geometrie. Addison-Wesley, Bonn, 1997.