Seminar Online-Algorithmen

Seminar WS 1999/2000
Susanne Albers und Ingo Wegener
044398 Di 14.15 - 16.00 Uhr, GB IV/318
Beginn: 12.10.1999
In der Informatik müssen oftmals Probleme gelöst werden, in denen zukünftige Eingaben oder Daten nicht bekannt sind. Solche Probleme heißen "Online-Probleme". Am einfachsten lässt sich die Situation an dem folgenden Beispiel aus dem "täglichen Leben" beschreiben. Ein Student möchte mit dem Skilaufen beginnen und steht vor der Wahl, ein Paar Ski für 50 DM zu leihen oder für 500 DM zu kaufen. Wie sollte er sich entscheiden, wenn er nicht weiß, wie lange er noch Skilaufen wird?

Klassische Online-Probleme in der Informatik treten in den folgenden Bereichen auf.

Paging, Caching: Gegeben ist ein zweistufiges Speichersystem bestehend aus einem kleinen schnellen Speicher und einem großen langsamen Speicher. Welche Speicherseiten sollen im schnellen Speicher gehalten werden, wenn nicht bekannt ist, welche Seiten als nächstes angefragt werden?

Datenverwaltung in verteilten Systemen: Wie sollen Dateien in einem Netzwerk verteilt werden, wenn nicht bekannt ist, welche Netzwerkknoten welche Dateien als nächstes benötigen?

Navigation und Exploration in der Robotik: Ein Roboter bewegt sich in einer unbekannten Umgebung und muss dabei ein ausgezeichnetes Ziel finden oder eine vollständige Karte erstellen.

Die Vergabe der Seminarthemen erfolgt bei Ingo Wegener (GB IV/333),

Seminarvorträge:

1. Grundlagen

Kapitel 1, 2, 3, 4 und 7 aus dem folgenden Buch. Allan Borodin und Ran El-Yaniv. Online computation and competitive analysis. Cambridge University Press, 1998.

2. Anwendungen

D.L. Black and D.D. Sleator. Competitive algorithms for replication and migration problems. Technical Report Carnegie Mellon University, CMU-CS-89-201, 1989.
J. Westbrook. Randomized algorithms for the multiprocessor page migration. SIAM Journal on Computing, 23:951--965, 1994.

A. Blum, P. Raghavan and B. Schieber. Navigating in unfamiliar geometric terrain. SIAM Journal on Computing, 26:110--137, 1997.
A. Blum, P. Berman, A. Fiat, H. Karloff, A. Rosen and M. Saks. Randomized robot navigation algorithms. Proc. 7th ACM-SIAM Symposium on Discrete Algorithms}, 75--84, 1996.

R. Motwani, S. Phillips and E. Torng. Non-clear-voyant scheduling. Proc. 4th Annual ACM-SIAM Symposium on Discrete Algorithms, 422--431, 1993.
D. Shmoys, J. Wein and D.P. Williamson. Scheduling parallel machines on-line. Proc. 32nd IEEE Annual Symposium on Foundations of Computer Science, 131--140, 1991.
Y. Azar, A. Broder and A. Karlin. On-line load balancing. Proc. 36th IEEE Symposium on Foundations of Computer Science, 218--225, 1992.

R. El-Yaniv, A. Fiat, R. Karp and G. Turpin, Competitive Analysis of Financial Games, Procedings of the 33rd Annual IEEE Symposium on Foundations of Computer Science, 327-333, 1992.

R. Karp, U. Vazirani and V. Vazirani. An optimal algorithm for online bipartite matching. Proc.~22nd ACM Symposium on Theory of Computing, 352--358, 1990.