English English

Termine

Termine / Ort
Beginn
Veranstalter
Mittwoch 15:30 - 17:00 im Raum 5056
09.04.2008
Matthias Westermann


Inhalt der Vorlesung

Viele Optimierungsprobleme sind NP-schwer, d.h. für diese Probleme kann kein Algorithmus mit polynomieller Laufzeit gefunden werden, der für alle Instanzen eine optimale Lösung berechnet, wenn P ungleich NP ist. Eine Möglichkeit, dieses Problem anzugehen, ist, auf eine optimale Lösung zu verzichten und nur eine approximative Lösung zu berechnen. Die Theorie der Approximationsalgorithmen beschäftigt sich mit dieser Möglichkeit.

Für viele andere Optimierungsprobleme kann auch kein Algorithmus gefunden werden, der für alle Instanzen eine optimale Lösung berechnet, weil die Eingabe vorab nicht bekannt ist, sondern erst zur Laufzeit präsentiert wird. Zum Beispiel kennt die Steuerungseinheit eines Lasten- oder Personenaufzugs typischerweise nicht alle Anfragen im Voraus, sondern diese werden erst nach und nach generiert. Die Theorie der Online-Algorithmen beschäftigt sich mit derartigen Problemen.

Die Vorlesung wird anhand ausgewählter Themen aus dem Bereich der Approximations- und Online-Algorithmen grundlegende Techniken und Konzepte dieser Gebiete der Algorithmik behandeln:

  • Listen
  • Suchbäume
  • Datenmanagement in Netzwerken
  • Lastbalancierung
  • Traveling-Salesperson-Problem

Skript


Literatur

  • Giorgio Ausiello, Pierluigi Crescenzi, Giorgio Gambosi, Viggo Kann, Alberto Marchetti-Spaccamela und Marco Protasi. Complexity and Approximation: Combinatorial Optimization Problems and Their Approximability Properties. Springer, 1999.
  • Allan Borodin und Ran El-Yaniv. Online Computation and Competitive Analysis. Cambridge University Press, 1998.
  • Thomas H. Cormen, Charles E. Leiserson und Ronald L. Rivest. Introduction to Algorithms. MIT Press/McGraw-Hill, 1990.
  • Dorit S. Hochbaum (Hrs.). Approximation Algorithms for NP-Hard Problems. PWS, 1996.
  • Vijay V. Vazirani. Approximation Algorithms. Springer, 2001.