Seminar
"Scheduling"
Wintersemester 2004/05 
Prof. Dr. Susanne Albers

Ort und Zeit: Di 16-18, SR 01-016 GB 101

Dieses Seminar richtet sich an Studierende des Hauptstudiums. Wir lesen aktuelle Arbeiten, die im Bereich des Schedulings und des Ressourcenmanagemants in den letzten ein bis zwei Jahren auf international führenden Tagungen publiziert wurden. Das Seminar ist theoretisch orientiert, d.h. die untersuchten Algorithmen werden hinsichtlich ihrer Güte mathematisch analysiert. Seminarteilnehmer sollten die Vorlesung Algorithmentheorie erfolgreich absolviert haben.

Die Teilnehmer des Seminars lesen selbstständig wissenschaftliche Papiere und stellen sie in einem 60-minütigen Vortrag den anderen Studierenden vor. Zusätzlich ist bis zum Vorlesungsende eine schriftliche Ausarbeitung von 8 bis 10 Seiten anzufertigen. Es werden 3 Kreditpunkte vergeben. 


Vortragsplan

• A. Gupta, A. Kumar und T. Roughgarden. Simpler and better approximation algorithms for network design. Proc. 35th ACM Symposium on Theory of Computing (STOC'03), 365-372, 2003.
   
• S. Albers und M. Schmidt. On the performance of greedy algorithms in packet buffering. Proc. 36th ACM Symposium on Theory of Computing (STOC'04), 35-44, 2004.
   
• Y. Azar und A. Litichevskey. Maximizing throughput in multi-queue switches. Proc. 12th Annual European Symposium on Algorithms (ESA'04), Springer LNCS 3221 53-64, 2004.
   
• Y. Azar und Y. Richter. An improved algorithm for CIOQ switches. Proc. 12th Annual European Symposium on Algorithms (ESA'04), Springer LNCS 3221 65-76, 2004.
   
• N. Bansal, L.K. Fleischer, T. Kimbrel, M. Mahdian, B. Schieber und M. Sviridenko. Further improvements in competitive guarantees for QoS buffering. Proc. 31st International Colloquium on Automata, Languages and Programming (ICALP'04), Springer LNCS 3142, 196-207, 2004.
   
• S. Irani, S. Shukla und R. Gupta. Algorithms for power savings. Proc. 14th Annual ACM-SIAM Symposium on Discrete Algorithms (SODA'03), 37-46, 2003.
   
• N. Bansal, T. Kimbrel und K. Pruhs. Dynamic speed scaling to manage energy and temperature. Proc. 45th Annual IEEE Symposium on Foundations of Computer Science (FOCS'04), 2004.
   
• J. Augustine, S. Irani und C. Swamy. Optimal power-down strategies. Proc. 45th IEEE Symposium on Foundations of Computer Science (FOCS'04), 2004.
   
• C. Brito, E. Koutsoupias und S. Vaya. Competitive analysis of organization networks or multicast acknowledgement: how much to wait? Proceedings of the 15th Annual ACM-SIAM Symposium on Discrete Algorithms (SODA'04), 627-635, 2004.