Technical Report No. 61, November 1994 - Abstract

Thomas Ottmann, Sven Schuierer, Christoph A. Hipke:
Kompetitive Analyse für Online-Algorithmen - Eine kommentierte Bibliographie

In vielen Anwendungen stellt sich das Problem, daß ein Algorithmus eine Folge von Anfragen bearbeiten muß und bei der Bearbeitung jeder Anfrage keine Information über die noch folgenden Anfragen hat. Solche Probleme heißen Online-Probleme. In den letzten Jahren ist eine Fülle von Arbeiten zu diesem Thema erschienen, wobei zur Analyse von Online-Algorithmen die kompetitive Analyse eingesetzt wird, d.h. es wird das Verhältnis der Kosten des Online-Algorithmus zu den optimalen Kosten betrachtet. Dieses Verhältnis wird als kompetitiver Faktor des Online-Algorithmus bezeichnet.

Diese Arbeit möchte einen Einblick geben in die Gebiete, die im Bereich der Online-Algorithmen untersucht werden, und die Ergebnisse, die bereits erzielt wurden. Da die kompetitive Analyse ein so allgemeines und viel benutztes Prinzip ist, kann natürlich kein Anspruch auf Vollständigkeit erhoben werden. Wir beschränken uns weitgehend auf neuere Arbeiten aus dem Gebiet der Online-Algorithmen, unsere Schwerpunkte bilden dabei die Darstellung der Grundlagen der kompetitiven Analyse und der theoretischen Modelle, sowie die Untersuchung geometrischer Online-Algorithmen