LEA
Fakultät für Informatik der Technischen Universität München
Lehrstuhl für Effiziente Algorithmen
Postadresse: 80290 München; Hausadresse: Arcisstr.21, 80333 München

Hauptseminar im WS2000/2001: Online Algorithmen und kompetitive Analyse

Vorbesprechung und Anmeldung:

Donnerstag, den 20. Juli 2000,
16:00 Uhr, Raum S2229


ES SIND NOCH PLÄTZE FREI!


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

`Online Computation and Competitive Analysis' von A. Borodin und R. El-Yaniv, Cambridge University Press 1998.



Themenliste






Weitere Auskünfte bei:

Alex Hall, Raum S2214, Tel: (089) 289-25342, Email: hall@in.tum.de
Thomas Schickinger, Raum S2214, Tel: (089) 289-25342, Email: schickin@in.tum.de