Inhalt

Fortgeschrittene Themen des Algorithmenentwurfs mit wechselnden Schwerpunkten. Der Inhalt ist nicht im Vorhinein bestimmt, sondern wird in jedem Semester neu festgelegt. Exemplarisch könnten Algorithmen für graphentheoretische Probleme, zum Beispiel über (mehrfachen) Zusammenhang, kürzeste Wege, Flüsse, behandelt werden.

Dieses Semester wird es hauptsächlich um Online- und Approximationsalgorithmen gehen.

Zielgruppe

Master-Studierende der Informatik oder Mathematik

Empfohlene Vorkenntnisse

Vorlesung "Höhere Algorithmik" oder vergleichbare Veranstaltung

Literatur

• V.V. Vazirani. Approximation Algorithms. Springer Verlag, 2001.
• D.P. Williamson and D.B. Shmoys. The Design of Approximation Algorithms. Cambridge University Press, 2010.
• A. Borodin and R. El-Yaniv. Online Computation and Competitive Analysis. Cambridge University Press, 1998.
• A. Fiat, G.J. Woeginger. Online Algorithms: The State of the Art. Springer Verlag, 1998.
• Buchbinder, Naor. The Design of Competitive Online Algorithms via a Primal-Dual Approach. Now Foundations and Trends, 2009.
• Spezialliteratur aus Zeitschriften