onlineVerfahren

OnlineVerfahren bezeichnen in der Informatik Verfahren und Algorithmen, die Eingaben sequenziell verarbeiten, sobald sie eintreten, ohne Kenntnis zukünftiger Daten. Im Gegensatz dazu stehen Offline-Verfahren, die den gesamten Eingabeumfang vorab kennen. Dieses Paradigma wird in Bereichen wie Streaming, Echtzeitsystemen und Online-Optimierung genutzt.

Typische Merkmale sind Entscheidungen in einem Sequenzfluss, begrenzter Speicherbedarf und Operationen, die auf dem aktuell verfügbaren Input basieren. Die Leistungsbewertung erfolgt oft durch Competitive Analysis, bei der das Verhältnis der Kosten eines Online-Verfahrens zu einem optimalen Offline-Verfahren gemessen wird. Es gibt auch randomized Online-Verfahren, die Zufall zur Entscheidungsfindung einsetzen.

Beispiele umfassen Paging- und Caching-Strategien, Online-Bipartite-Matching, Scheduling-Algorithmen und das Online-Streaming-Modell, bei dem Daten in begrenztem Speicher verarbeitet werden. In der Praxis kommen Online-Verfahren oft zur Ressourcenzuweisung, Netzwerkrouting und Lastverteilung zum Einsatz.

Typische Anwendungen finden sich im Netzwerkrouting, in Web-Caching-Systemen, in Echtzeitsystemen sowie in der Analyse von Online-Lern- und Online-Optimierungsverfahren.

Historisch formten Sleator und Tarjan 1985 die Competitive Analysis als formalen Bewertungsrahmen für Online-Verfahren, der das Worst-Case-Verhältnis der Online- gegenüber der Offline-Leistung misst. Seitdem hat das Gebiet zahlreiche Modelle und Anwendungen hervorgebracht.