|
|
|
|
|
Im Rahmen dieses Hauptseminars soll ein Überblick über ausgewählte Probleme aus dem Gebiet der Online Algorithmen gegeben werden. Bei einem Online Problem geht man davon aus, dass der Algorithmus anfangs noch nicht die gesamte Eingabe "kennt", sondern dass ihm diese erst nach und nach geliefert wird. Beispiel: der Scheduler eines Betriebssystems weiss nicht von anfang an, welche Prozesse er in Zukunft zu schedulen hat. Es ist intuitiv klar, dass ein Online Algorithmus somit benachteiligt ist und nicht unbedingt eine optimale Loesung errechnen kann. Man interessiert sich deswegen fuer die relative Guete einer Online Loesung im Vergleich zur Loesung eines optimalen Offline Algorithmus. Dies wird auch als kompetitive Analyse bezeichnet. Meist stellt man sich bei der Analyse einen Gegenspieler vor, der dem Algorithmus immer möglichst "gemeine" Eingaben liefert, bei denen seine Loesung im Vergleich zur optimalen maximal schlecht wird.
Unsere Arbeitsvorlage ist