Lehrstuhl Informatik 1
Algorithmen und Komplexität
Prof. Dr. Berthold Vöcking

Lehrstuhl i1

• » Startseite
• » Adresse
• » Personen

Forschung

• » Schwerpunkte
• » Projekte
• » Veröffentlichungen

Lehre

• » Vorlesungsangebot
• » Winter 09/10
• » Sommer 09
• » Frühere Semester
• » Diplomprüfungen

Abschlussarbeiten

• » Bachelor
• » Diplom/Master
• » Promotionen

Links

• » i1 intern
• » Schulprojekt
• » Fachgruppe
• » RWTH Aachen
• » Campus
• » Webmail

Sonstiges

• » Haftung

Veranstalter

Helge Bals, Matthias Englert, Matthias Westermann

---

Termine

• Dienstag 9. August, 15:00 Uhr, Raum 4017: Kurzpräsentation (maximal 4 Minuten pro Teilnehmer)
• Freitag 16. September: Abgabe der  Ausarbeitungen  (maximal 4 Seiten pro Teilnehmer)
• Montag 26. - Mittwoch 28. September, Raum 4017: Vorträge (45 Minuten pro Teilnehmer, inklusive Diskussion)

	Montag	Dienstag	Mittwoch
14:00 - 15:30	TCP-Acknowledgment	Metrical-Task-Systems und das k-Server-Problem	Quality of Service Buffering
15:45 - 17:15	Lastverteilung	Bartals Baum-Metrik	Reordering Buffer
17:30 - 18:15	Alternative Paging-Modelle	Datenmanagement in Netzwerken

 

---

Inhalt

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 Gruppenarbeit einem Vortrag von 45-90 Minuten Dauer (ca. 45 Minuten je Teilnehmer) zu einem Thema ausarbeiten. Der Inhalt sollte möglichst verständlich präsentiert werden. Der Vortrag sollte dabei nicht vornehmlich den Seminarleiter ansprechen sondern insbesondere Ihre Komilitonen.

---

Vorlage für die Ausarbeitung

• beispiel.tex und papers.bib

---

Themen

• Datenmanagement in Netzwerken: [MMVW97] und [MVW99]
  Arne Rache, Betreuer: Matthias Westermann
  
  
• Bartals Baum-Metrik: [B96] und [FRT03]
  Robert Igelmund, Betreuer: Matthias Englert
  
  
• Alternative Paging-Modelle: Kapitel 5 aus [BE98]
  Linlin Cai, Betreuer: Helge Bals
  
  
• Metrical-Task-Systems und das k-Server-Problem: Kapitel 9 und 10 aus [BE98]
  Frank Pöttgen und Tobias Schierge, Betreuer: Matthias Westermann
  
  
• Lastverteilung: Kapitel 12 aus [BE98] und [AAF+97]
  Christian Guggenmos und Jörg Jörgens, Betreuer: Helge Bals
  
  
• TCP-Acknowledgment: [DGS01], [S00], [KKR01] und [AB03]
  Christopher Vogt und Marc Wu, Betreuer: Helge Bals
  
  
• Quality of Service Buffering: [KLM+01] und [AR03]
  Alexander Becher und Achim Passen, Betreuer: Matthias Englert
  
  
• Reordering Buffer: [EW05] und [KRS+04]
  Rene Boulnois und Florian Hermisch, Betreuer: Matthias Englert

---

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.
  
  
• [AB03]: Susanne Albers und Helge Bals. Dynamic TCP acknowledgement: Penalizing long delays . In Proc. of the 14th ACM-SIAM Symp. on Discrete Algorithms (2003), 47-55.
  
  
• [AR03]: Yossi Azar und Yossi Richter. Management of multi-queue switches in QoS networks . In Proc. of the 35th Ann. ACM Symp. on Theory of Computing (2003), 82-89. 
  
  
• [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), 184-193.
  
  
• [BE98]: Allan Borodin und Ran El-Yaniv. Online Computation and Competitive Analysis. Cambridge University Press, 1998.
  
  
• [DGS01]: Daniel Dooly, Sally Goldman und Stephen Scott. On-line analysis of the TCP acknowledgment delay problem . Journal of the ACM 48 (2001), 243-273.
  
  
• [EW05]: Matthias Englert und Matthias Westermann. Reordering Buffer Management for Non-Uniform Cost Models . In Proc. of the 32nd Int. Colloquium on Automata, Languages and Programming (2005), 627-638.

• [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.
  

• [KKR01]: Anna R. Karlin, Claire Kenyon, Dana Randall. Dynamic TCP-Acknowledgment and other stories about e/(e - 1) ( full version ). In Proc. of the 33th Ann. ACM Symp. on Theory of Computing (2001), 502-509.
  
  
• [KLM+01]: Alexander Kesselman, Zvi Lotker, Yishay Mansour, Boaz Patt-Shamir, Baruch Schieber und Maxim Sviridenko. Buffer Overflow Management in QoS Switches . In Proc. of the 33th Ann. ACM Symp. on Theory of Computing (2001), 520-529.
  
  
• [KRS+04]: Jens Krokowski, Harald Räcke, Christian Sohler und Matthias Westermann. Reducing State Changes with a Pipeline Buffer . In Proc. of the 9th Int. Fall Workshop Vision, Modeling, and Visualization (2004), 217-224.
  
  
• [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.
  
  
• [MVW99]: Friedhelm Meyer auf der Heide, Berthold Vöcking und Matthias Westermann. Provably Good and Practical Strategies for Non-Uniform Data Management in Networks . In Proc. of the 7th Ann. European Symp. on Algorithms (1999), 89-100.
  
  
• [S00]: Steven Seiden. A guessing game and randomized online algorithms . In Proc. of the 32nd Ann. ACM Symp. on Theory of Computing (2000), 592-601.

---