Vorlesung Approximations- und Online-Algorithmen

• Dozent: Univ.-Prof. Dr. Rob van Stee
• Termin: Wöchentlich mittwochs, 11.30 - 13.00 Uhr
• Ort: Seminarraum 301, Informatik-Hauptgebäude

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.