Online-Algorithmen

Online-Algorithmen müssen unwiderrufliche Entscheidungen treffen, sobald Eingaben eintreffen, ohne Kenntnis zukünftiger Anfragen; ihre Qualität wird durch eine kompetitive Analyse im Vergleich zu einem optimalen Algorithmus gemessen, der die gesamte Eingabe im Voraus kennt.

Definition

Ein Online-Algorithmus empfängt seine Eingabe als eine Sequenz von Anfragen und muss auf jede sofort und unwiderruflich reagieren, ohne zukünftige Anfragen zu kennen; sein kompetitives Verhältnis ist das Worst-Case-Verhältnis seiner Kosten zu den Kosten eines optimalen Offline-Algorithmus, der die gesamte Anfragesequenz kennt.

Scope

Dieses Thema behandelt Algorithmen, die Eingaben sequenziell verarbeiten und Entscheidungen treffen, bevor spätere Eingaben bekannt sind, sowie den Rahmen der kompetitiven Analyse, der verwendet wird, um sie gegen einen optimalen Offline-Gegner zu bewerten. Es umfasst klassische Probleme – Paging und Caching, Listenaktualisierung, das Ski-Rental-Problem, das k-Server-Problem sowie Online-Scheduling und Bin Packing – und die Rolle der Randomisierung bei der Verbesserung kompetitiver Verhältnisse gegenüber schwächeren Gegnern.

Core questions

• Wie werden Online-Algorithmen bewertet, wenn die Zukunft unbekannt ist?
• Was misst das kompetitive Verhältnis, und was ist der Offline-Gegner?
• Wie illustrieren klassische Probleme wie Paging und Ski-Rental Online-Kompromisse?
• Wie kann Randomisierung die Wettbewerbsfähigkeit gegenüber einem ahnungslosen Gegner verbessern?
• Welche unteren Schranken begrenzen, wie wettbewerbsfähig ein Online-Algorithmus sein kann?

Key concepts

• online versus offline
• kompetitives Verhältnis
• Offline-Gegner
• Paging und Caching
• Listenaktualisierung
• Ski-Rental-Problem
• k-Server-Problem
• randomisierte Wettbewerbsfähigkeit

Key theories

Kompetitive Analyse

Die kompetitive Analyse beurteilt einen Online-Algorithmus anhand des Worst-Case-Verhältnisses zwischen seinen Kosten und denen eines optimalen Offline-Algorithmus, wodurch eine Garantie gegeben wird, die für jede Eingabesequenz gilt, anstatt sich auf Annahmen über die Eingabe zu verlassen.

Randomisierung gegen ahnungslose Gegner

Randomisierte Online-Algorithmen können streng bessere kompetitive Verhältnisse erzielen als jeder deterministische Algorithmus gegen einen ahnungslosen Gegner, da der Gegner die Eingabe festlegen muss, ohne die zufälligen Entscheidungen des Algorithmus zu kennen.

Clinical relevance

Online-Algorithmen modellieren Entscheidungen, die Systeme in Echtzeit ohne zukünftiges Wissen treffen: Cache- und Seitenersetzung in Betriebssystemen und CPUs, Selbstorganisation von Datenstrukturen, dynamische Ressourcenzuweisung und Lastverteilung sowie Miet- oder Kaufentscheidungen im Cloud Computing. Die kompetitive Analyse bietet Worst-Case-Garantien für solche reaktiven Systeme.

History

Die kompetitive Analyse wurde 1985 von Sleator und Tarjan durch ihre Untersuchung von Listenaktualisierungs- und Paging-Regeln eingeführt, wodurch die Bewertung von Online-Algorithmen auf den Vergleich mit einer optimalen Offline-Lösung neu ausgerichtet wurde. Der Rahmen wurde in den 1990er Jahren durch das k-Server-Problem und randomisierte Online-Algorithmen erweitert, die in der Monographie von Borodin und El-Yaniv aus dem Jahr 1998 zusammengefasst sind.

Key figures

• Daniel Sleator
• Robert Tarjan
• Allan Borodin
• Ran El-Yaniv

Seminal works

• sleator1985
• borodin1998
• cormen2009

Frequently asked questions

Was ist das kompetitive Verhältnis?

Es ist das Worst-Case-Verhältnis der Kosten eines Online-Algorithmus zu den Kosten eines optimalen Algorithmus, der die gesamte Eingabe im Voraus kennt. Ein 2-kompetitiver Algorithmus kostet niemals mehr als das Doppelte der bestmöglichen Offline-Kosten für jede Eingabesequenz.

Warum hilft Randomisierung Online-Algorithmen?

Gegen einen ahnungslosen Gegner, der die Eingabe festlegt, ohne die zufälligen Entscheidungen des Algorithmus zu kennen, verhindert die Randomisierung, dass der Gegner einen Worst Case auf das Verhalten des Algorithmus zuschneidet, was streng bessere kompetitive Verhältnisse ermöglicht, als jeder deterministische Algorithmus erreichen kann.