Institut für Theoretische Informatik, Algorithmik

Seminar: Approximationsschemata in Ablaufplanung, Graphentheorie und Geometrie

Sommersemester 2005

Allgemeines

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

  1. Frank Hoffmann and Christian Knauer. Wie gestalte ich einen Seminarvortrag? Freie Universität Berlin, 1998. [pdf]
  2. Petra Schuurman and Gerhard J. Woeginger. Approximation Schemes - A Tutorial. Technical Report Woe-65, TU Graz, 2001. [pdf]
  3. Sanjeev Arora. Approximation schemes for NP-hard geometric optimization problems: a survey. Mathematical Programming, 97(1-2):43-69, July 2003.
  4. 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.
  5. 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.
  6. Brenda S. Baker. Approximation Algorithms for NP-Complete Problems on Planar Graphs. Journal of the ACM, 41(1):153-180, 1994.
  7. Mark de Berg, Marc van Kreveld, Mark Overmars, and Otfried Schwarzkopf. Computational Geometry: Algorithms and Applications. Springer-Verlag, Berlin, 1997.
  8. Rolf Klein. Algorithmische Geometrie. Addison-Wesley, Bonn, 1997.