SIGACT news online algorithms column 4

ABSTRACT

<b>From the editor:</b> This issue's column contains an expository article by Leah Eppstein and Rob Van Stee on models and algorithms for buffer management in QofS networks. This area has seen a flurry of activity in the last four years. In spite of good progress, several fundamental, easy-to-state problems remain open. Many thanks to Leah and Rob for this timely contribution.

REFERENCES

• 1: William A. Aiello, Yishay Mansour, S. Rajagopolan, and Adi Rosen. Competitive queue policies for differentiated services. In Proc. of the IEEE INFOCOM, pages 431--440, 2000.
• 2: Susanne Albers , Markus Schmidt, On the performance of greedy algorithms in packet buffering, Proceedings of the thirty-sixth annual ACM symposium on Theory of computing, June 13-16, 2004, Chicago, IL, USA [doi>10.1145/1007352.1007366]
• 3: Nir Andelman , Yishay Mansour , An Zhu, Competitive queueing policies for QoS switches, Proceedings of the fourteenth annual ACM-SIAM symposium on Discrete algorithms, January 12-14, 2003, Baltimore, Maryland
• 4: Yossi Azar and Arik Litichevskey. Maximizing throughput in multi-queue switches. In Algorithms - ESA 2004, Proceedings Twelfth Annual European Symposium, Lecture Notes in Computer Science. Springer, 2004. To appear.
• 5: Yossi Azar , Yossi Richter, Management of multi-queue switches in QoS networks, Proceedings of the thirty-fifth annual ACM symposium on Theory of computing, June 09-11, 2003, San Diego, CA, USA [doi>10.1145/780542.780556]
• 6: Yossi Azar , Yossi Richter, The zero-one principle for switching networks, Proceedings of the thirty-sixth annual ACM symposium on Theory of computing, June 13-16, 2004, Chicago, IL, USA [doi>10.1145/1007352.1007369]
• 7: Yair Bartal, Francis Y. L. Chin, Marek Chrobak, Stanley P. Y. Fung, Wojciech Jawor, Ron Lavi, Jiří Sgall, and Tomáš Tichý. Online competitive algorithms for maximizing weighted throughput of unit jobs. In Proc. 21st Symp. on Theoretical Aspects of Computer Science (STACS), pages 187--198, 2004.
• 8: Allan Borodin , Ran El-Yaniv, Online computation and competitive analysis, Cambridge University Press, New York, NY, 1998
• 9: Francis Y. L. Chin and Stanley P. Y. Fung. Online scheduling for partial job values: Does timesharing or randomization help? Algorithmica, 37:149--164, 2003.
• 10: Marek Chrobak, Wojciech Jawor, Jiří Sgall, and Tomáš Tichý. Improved online algorithms for buffer management in QoS switches. In Algorithms - ESA 2004, Proceedings Twelfth Annual European Symposium, Lecture Notes in Computer Science. Springer, 2004. To appear.
• 11: B. Hajek. On the competitiveness of online scheduling of unit-length packets with hard deadlines in slotted time. In Conference in Information Sciences and Systems, pages 434--438, 2001.
• 12: Alexander Kesselman , Zvi Lotker , Yishay Mansour , Boaz Patt-Shamir , Baruch Schieber , Maxim Sviridenko, Buffer Overflow Management in QoS Switches, SIAM Journal on Computing, v.33 n.3, p.563-583, 2004 [doi>10.1137/S0097539701399666]
• 13: Alex Kesselman, Yishay Mansour, and Rob van Stee. Improved competitive guarantees for QoS buffering. In Algorithms - ESA 2003, Proceedings Eleventh Annual European Symposium, volume 2380 of Lecture Notes in Computer Science, pages 361--373. Springer, 2003.
• 14: Alex Kesselman , Adi Rosén, Scheduling policies for CIOQ switches, Proceedings of the fifteenth annual ACM symposium on Parallel algorithms and architectures, June 07-09, 2003, San Diego, California, USA [doi>10.1145/777412.777473]
• 15: Tracy Kimbrel. A simple proof of the 2-competitiveness of the greedy FIFO buffering algorithm. Technical Report RC23272, IBM Research, 2004.
• 16: Mohammad Mahdian, Nikhil Bansal, Lisa K. Fleischer, Tracy Kimbrel, Baruch Schieber, and Maxim Sviridenko. Further improvements in competitive guarantees for QoS buffering. In Proc. 31st International Colloquium on Automata, Languages, and Programming (ICALP), 2004.
• 17: Yishay Mansour , Boaz Patt-Shamir , Ofer Lapid, Optimal smoothing schedules for real-time streams (extended abstract), Proceedings of the nineteenth annual ACM symposium on Principles of distributed computing, p.21-29, July 16-19, 2000, Portland, Oregon, United States [doi>10.1145/343477.343511]