Description

Es gibt viele praktische Probleme, die nicht perfekt gelöst werden können oder bei denen 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 dex Input, 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 trifft, 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 man kann beim Scheduling von Jobs auf Maschinen nicht immer warten, bis alle Jobs da sind, bevor man anfängt, Jobs 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.

Vorläufige Themenliste

    * TSP, Steinerbäume
    * Rucksackproblem
    * Vertex cover: lineare Programmierung
    * Routing: Randomisierung
    * max cut: lokale Suche
    * Scheduling

In der zweite Hälfte der Vorlesung werden diese und auch andere Probleme als Online-Probleme betrachtet.