Institut für Theoretische Informatik, Algorithmik

Vorlesung Approximations- und Online-Algorithmen

Sommersemester 2010

Allgemeines

Aktuelles

Wie komme ich mit meiner Unfähigkeit und meinem Unwissen zurecht?

Es gibt viele praktische Probleme, die nicht perfekt gelöst werden können oder für die es sehr lange dauern würde, eine optimale Lösung zu finden. Ein Beispiel dafür ist Bin-Packing, wo Objekte in Behältern (bins) einzupacken sind, wobei man möglichst wenige Behälter benutzen will.

In solchen Fallen sind wir daran interessiert, möglichst einfache Algorithmen zu entwerfen, die in angemessener Rechenzeit „fast“ perfekte Lösungen ergeben. Solche Algorithmen heißen Approximationsalgorithmen. Die Rechenzeit eines Approximationsalgorithmus sollte polynomiell sein in der Größe des Inputs, und das Ergebnis sollte von der optimalen Lösung um nicht mehr als einen bestimmten Faktor abweichen.

Außerdem gibt es oft Probleme, bei denen man Entscheidungen treffen möchte, ohne vollständige Kenntnis über die Zukunft oder die Gegenwart zu haben. Man möchte etwa beim Bin-Packing irgendwann auch Bins abschließen und wegschicken, während vielleicht noch neue Objekte ankommen. Oder beim Scheduling von Jobs auf Maschinen kann man nicht immer warten, bis alle Jobs da sind, bevor man anfängt Jobs an Maschinen zuzuweisen und auszuführen.

Wie sollte man in solchen Fallen Entscheidungen treffen?

Mit dieser Frage beschäftigen sich wir uns in dieser Vorlesung. Wir werden Online-Algorithmen zeigen, die ohne Kenntnis der Zukunft trotzdem gute Lösungen liefern.

Material

Thema Datum Folien
Einführung, Scheduling 14.04. pdf
Traveling Salesman Problem 21.04. pdf
Knapsack 28.04. pdf
Vertex Cover, Scheduling 05.05. pdf
Vertex Coloring 12.05. pdf
Bin-Packing, Scheduling-PTAS 19.05. pdf
Online-Algorithmen 26.05. pdf
Caching 2.06. pdf
k-Server 9.06. pdf
Online Bin-Packing 16.06 pdf
Multidimensionales Bin-Packing 23.06 pdf
Multidimensionales Bin-Packing 30.06
Online Load-Balancing 07.07 pdf
k-Center 14.07 pdf