Seminar
"Online-Algorithmen"
Wintersemester 2001/02
Prof. Dr. Susanne Albers

Die Vergabe der Seminarthemen erfolgt bei Susanne Albers (GB 79, Zimmer 010).

In der Informatik müssen oftmals Probleme gelöst werden, in denen zuknüftige Eingaben oder Daten nicht bekannt sind. Solche Probleme heißen Online-Probleme . Am einfachsten läßt 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 Winter 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?

Datenstrukturen: Wie sollte eine lineare Liste oder ein binärer Baum verwaltet werden, wenn nicht bekannt ist, auf welche Elemente als nächstes zugegriffen wird? Ziel ist die Entwicklung von sich selbst organisierenden Strukturen.

Robotik: Ein Roboter bewegt sich in einer unbekannten Umgebung und muß dabei ein ausgezeichnetes Ziel finden oder eine vollständige Karte erstellen. Die dabei zurückgelegte Wegstrecke soll dabei so gering wie möglich sein.

Netzwerke: Wie sollten die Ressourcen, z.B. die TCP-Verbindungen in einem Netzwerk verwaltet werden, wenn nicht bekannt ist, welche Verbindungen als nächstes benötigt werden? Ziel ist es, möglichst gute Antwortzeiten im Netz zu garantieren.Seminarvorträge

• Grundlagen:
  
  Ausgewählte Kapitel aus dem Buch: Allan Borodin und Ran El-Yaniv. Online computation and competitive analysis. Cambridge University Press, 1998.
  
  
  • Selbstorganisierende Listen
    Kapitel 1 und 2
    
    
  • Paging
    Kapitel 3 und 4
    
    
  • Randomisierung in Online-Algorithmen
    Kapitel 7
    
    
• Anwendungen:
  
  
  • TCP-Acknowledgment in Netzwerken
    S.A. Goldman, D. Dooly and S. Scott. TCP Dynamic acknowledgement delay: theory and practice. Proc. 30th Annual ACM Symposium on Theory of Computing Seiten 289-298, 1998.
    A.R. Karlin, C. Kenyon and D. Randall. Dynamic TCP acknowledgement and other stories about e/(e-1). 33rd Annual ACM Symposium on Theory of Computing, 2001.
    
    
  • Connection-Caching im WWW
    E. Cohen, H. Kaplan und U. Zwick. Connection caching. Proc. of the 31st Annual ACM Symposium on Theory of Computing, Seiten 612-621, 1999.
    S. Albers. Generalized connection caching. Proc. 12th Annual ACM Symposium on Parallel Algorithms and Architectures, Seiten 70-78, 2000.
    
    
  • Dokumentencaching im WWW
    N.E. Young. Online file caching. Proc. 9th Annual ACM-SIAM Symposium on Discrete Algorithms, Seiten 82-86, 1998.
    
    
  • Roboter-Navigation
    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, Seiten 75--84, 1996.
    
    
  • Scheduling und Lastbalancierung
    R. Motwani, S. Phillips and E. Torng. Non-clearvoyant scheduling. Proc. 4th Annual ACM-SIAM Symposium on Discrete Algorithms, Seiten 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, Seiten 131-140, 1991.
    Y. Azar, A. Broder and A. Karlin. On-line load balancing. Proc. 36th IEEE Symposium on Foundations of Computer Science, Seiten 218-225, 1992.