Blockseminar: Online-Algorithmen

im Wintersemester 2003/2004

Helge Bals, Berthold Vöcking, Matthias Westermann

In der Informatik müssen oftmals Probleme gelöst werden, in denen Eingaben oder Daten nicht vorab bekannt sind, sondern erst zur Laufzeit präsentiert werden. Zum Beispiel kennt die Steuerungseinheit eines Lasten- oder Personenaufzugs typischerweise nicht alle Anfragen im Voraus, sondern die einzelnen Anfragen werden erst nach und nach bekanntgegeben. Derartige Probleme heißen Online-Probleme. In diesem Seminar sollen ausgewählte Themen aus dem Bereich der Online-Algorithmen bearbeitet und vorgestellt werden.

Als Teilnehmer werden Sie in einem Vortrag von ca. 90 Minuten Dauer Ihr Thema Ihren Kommilitonen vermitteln. Zusätzlich ist eine Ausarbeitung zu erstellen.

Die Vorträge finden vom 9.2. - 11.2.2004 im Raum GB4-113 statt. Die in Latex erstellten Ausarbeitungen sind bis zum Ende der vorlesungsfreien Zeit abzugeben.

Programm

• Montag 9.2.
• 13.00 - 14.30 List-Accessing
  
• 15.00 - 16.30 Paging
• 16.30 - 17.15 TCP-Acknowledgment
• Dienstag 10.2.
• 14.00 - 15.30 Metrical-Task-Systems und das k-Server-Problem
  
• 16.00 - 17.30 Load-Balancing
• Mittwoch 11.2.
• 14.00 - 15.30 Bartals Baum-Metrik
• 16.00 - 17.30 Robot-Navigation

Themen

• List-Accessing: Kapitel 1 und 2 aus [BE98]
  2 Personen, Schwierigkeitsgrad +, Betreuer M. Westermann
  Daniel Saltmann und Miriam Padberg
  
  
• Paging: Kapitel 3 und 4 aus [BE98]
  2 Personen, Schwierigkeitsgrad +, Betreuer B. Vöcking
  Philip Geismann und Mirjana Lukic
  
  
• Alternative Paging-Modelle: Kapitel 5 aus [BE98]
  2 Personen, Schwierigkeitsgrad +++, Betreuer M. Westermann
  
  
• Metrical-Task-Systems und das k-Server-Problem: Kapitel 9 und 10 aus [BE98]
  2 Personen, Schwierigkeitsgrad ++, Betreuer M. Westermann
  Tycho Moencks und Torsten Seyfarth
  
  
• Bartals Baum-Metrik: [B96] und [FRT03]
  2 Personen, Schwierigkeitsgrad +++, Betreuer B. Vöcking
  Matthias Englert und Patrick Briest
  
  
• Datenmanagement in Netzwerken: [MMVW97]
  2 Personen, Schwierigkeitsgrad ++, Betreuer M. Westermann
  
  
• TCP-Acknowledgment: [DGS98]
  1 Person (nur 45 min Vortrag), Schwierigkeitsgrad +, Betreuer H. Bals
  Ponyan Ghanbarian
  
  
• Load-Balancing: Kapitel 12 aus [BE98] und [AAF+97]
  2 Personen, Schwierigkeitsgrad ++, Betreuer B. Vöcking
  Andreas Ehrenberg und Seung-Jun Hong
  
  
• Trading und Portfolio-Selection: Kapitel 14 aus [BE98]
  2 Personen, Schwierigkeitsgrad ++, Betreuer M. Westermann
  
  
• Robot-Navigation: [BRS97]
  2 Personen, Schwierigkeitsgrad ++, Betreuer H. Bals
  Madeleine Theile und Detlev Bartsch
  

Literatur

• [AAF+97]: James Aspnes, Yossi Azar, Amos Fiat, Serge Plotkin und Orli Waarts. On-line load balancing with applications to machine scheduling and virtual circuit routing. Journal of the ACM 44 (1997), 486-504.
  

• [B96]: Yair Bartal. Probabilistic Approximation of Metric Spaces and its Algorithmic Applications. In Proc. of the 37th Ann. IEEE Symp. on Foundations of Computer Science (1996).
  
  
• [FRT03]: Jittat Fakcharoenphol, Satish Rao und Kunal Talwar. A tight bound on approximating arbitrary metrics by tree metrics. In Proc. of the 35th Ann. ACM Symp. on Theory of Computing (2003), 448-455.
  
  
• [BRS97]: Avrim Blum, Prabhakar Raghavan und Baruch Schieber. Navigating in Unfamiliar Geometric Terrain. SIAM Journal on Computing 26 (1997), 110-137.
  
  
• [BE98]: Allan Borodin und Ran El-Yaniv. Online Computation and Competitive Analysis. Cambridge University Press, 1998. (vorhanden in LS2-Bibliothek)
  
  
• [DGS98]: Daniel Dooly, Sally Goldman und Stephen Scott. TCP Dynamic Acknowledgement Delay: Theory and Practice (full version). In Proc. of the 30th Ann. ACM Symp. on Theory of Computing (1998) 289-298.
  

• [MMVW97]: Bruce Maggs, Friedhelm Meyer auf der Heide, Berthold Vöcking und Matthias Westermann. Exploiting Locality for Data Management in Systems of Limited Bandwidth (full version). In Proc. of the 38th Ann. IEEE Symp. on Foundations of Computer Science (1997), 284-293.