Vorlesung über "Approximations- und Online-Algorithmen"

Termine

Erste Veranstaltung ist am Donnerstag, dem 28.10.2004. Die Vorlesung findet donnerstags von 11.45 bis 13.15 im Seminarraum 616, im Pohlighaus, statt.

Inhalte der Vorlesung

Der Entwurf von effizienten Algorithmen ist eine zentrale Aufgabe in der Informatik. Während in den Veranstaltungen des Grundstudiums Informatik effiziente algorithmische Lösungen für grundlegende Probleme vorgestellt wurden und in der Vorlesung über Theoretische Informatik die Grenzen der Algorithmik beleuchtet wurden, ist das Ziel dieser Vorlesung über "Approximatinons- und Online-Algorithmen" effiziente Algorithmen zu entwicklen, um Näherungslösungen für schwere Probleme zu erhalten.

Schwerpunkte

Die Schwerpunkte der zweistündigen Vorlesung liegen auf den folgenden Gebieten:

Approximationsalgorithmen: Von vielen in der Praxis auftretenden Optimierungsproblemen ist zu erwarten, daß sie nicht in Polynomialzeit lösbar sind. Falls der Wunsch nach einer exakten Lösung für schwere Optimierungsprobleme abgeschwächt wird und man stattdessen probiert, eine Näherungslösung zu bestimmen, so wird durch diese Relaxierung häufig eine effiziente algorithmische Behandlung des schweren Problems ermöglicht. In diesem Teil der Vorlesung sollen effiziente Approximationsverfahren für verschiedene Probleme und die Analyse der Qualität der erhaltenen Lösungen vorgestellt werden.

Online-Algorithmen: Beim klassischen Algorithmenentwurf geht man davon aus, daß die zur Lösung eines Problems benötigten Daten zu Beginn der Berechnungen vollständig vorliegen. In vielen praktischen Problemen treffen Eingabedaten jedoch online, d.h. nach und nach ein. Typische Probleme sind etwa, welche Daten bei Minimierung der Zugriffszeit im Cache gespeichert bleiben sollen und welche gelöscht werden sollen, oder aber auch, wann es sinnvoll ist, etwa eine Bahncard zu kaufen, vor/nach der ersten, zweiten usw. Fahrt. Ein in diesem Online-Kontext entworfener Algorithmus stellt eine Näherungslösung für einen bestmöglichen Offline-Algorithmus dar.

Scheinerwerb

Aufbauend auf dieser Vorlesung ist für das Sommersemester 2005 ein gleichnamiges Seminar in Planung, in dem es möglich sein wird, einen Seminarschein zu erwerben.

Literatur

• D. S. Hochbaum, Approximation Algorithms for NP-hard Problems, PWS Publishing Company, 1997;
• A. Borodin, R. El-Yaniv. Online Computation and Competitive Analysis. Cambr. Univ. Press, 1998;
• V.V. Vazirani, Approximation Algorithms, Springer Verlag, 2001.