Vorlesung

Approximations- und Online-Algorithmen

oder

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 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, wo 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 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.

Vorläufige Themenliste

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

Materialien

  1. Folien, Text über den LPT Algorithmus
  2. Folien TSP und Steinerbäume. Text über den Return Home-Algorithmus.
  3. Folien Rucksackproblem
  4. Folien Vertex Cover und Scheduling Unrelated Machines
  5. Folien Bin Packing und Load Balancing. Conference talk on a memory allocation problem
  6. Folien Vertex Coloring
  7. Folien Ski Rental, Cow Path und List Update. Artikel über Google
  8. Folien Paging, Randomisierte Algorithmen
  9. Folien Local Search: Maximum Cut and Edge Coloring. Conference talk on Multigraph Edge Coloring.
  10. Folien k-Server Problem
  11. Folien Online Bin-Packing
  12. Folien Multidimensionales Bin-Packing
  13. Folien Online Load-Balancing
  14. Folien k-center Problem