Approximationsalgorithmen

Prüfungstermine: Geprüft wird am 9. und 10.Oktober. Hier ist die Liste der Termine für die Kandiaten.

Beschreibung:

Für viele kombinatorische Optimierungsprobleme hat sich herausgestellt, daß sie vermutlich nicht durch schnelle exakte Algorithmen gelöst werden können, weshalb man sich mit Näherungslösungen zufrieden geben muß. In dieser Vorlesung werden Approximationsalgorithmen vorgestellt, die für eine Reihe populärer Optimierungsprobleme beweisbar gute Lösungen in vertretbarer Zeit berechnen.

Im ersten Teil der Veranstaltung werden die grundlegenden Begriffe vorgestellt, mit Beispielalgorithmen ausgeführt und jeweils die Grenzen aufgezeigt.

Im zweiten Teil werden allgemeine Techniken eingeführt und anhand instruktiver Beispiele mit Leben erfüllt.

Literatur:

• R. Wanka. Approximationsalgorithmen - Eine Einführung Teubner, 2006.
• K. Jansen, M. Margraf. Approximative Algorithmen und Nichtapproximierbarkeit. de Gruyter, 2008
• G. Ausiello, P. Crescenzi, G. Gambosi, V. Kann, A. Marchetti-Spaccamela, M. Protasi. Complexity and Approximation - Combinatorial Optimization Problems and Their Approximability Properties. Springer, 1999.
• E. W. Mayr, H. J. Prömel, and A. Steger (Hrsg.). Lectures on Proof Verification and Approximation Algorithms. Springer, 1998.
• V. V. Vazirani. Approximation Algorithms. Springer, 2001.

Inhalte:

• Grundlagen
  • Schnelle Algorithmen und hartnäckige Probleme
  • Approximation mit absoluter Güte
  • Approximation mit relativer Güte
  • Approximationsschemata
• Techniken
  • Randomisierte Approximationsalgorithmen
  • Lineare Optimierung und Approximationsalgorithmen
  • Approximate Counting und die Monte-Carlo-Methode

• Zu Aufgabe 6: Nineteen Proofs of Euler's Formula, gesammelt von David Eppstein.
• Zu Aufgabe 8: Die Webseite bei Intel zu Moore's Law.

Übungsblätter: