Students Win Best Student Paper Award at SODA 10
University of Illinois computer science PhD students Sungjin Im and Benjamin Moseley recently received honors for their work on developing and analyzing an algorithm for broadcast scheduling. Their paper, "An Online Scalable Algorithm for Average Flow Time in Broadcast
Scheduling", received the Best Student Paper award at the ACM-SIAM Symposium on Discrete Algorithms (SODA 2010), the premiere computer science conference on discrete algorithms. The paper is available at http://www.cs.uiuc.edu/homes/bmosele2/papers/ScalableJ.pdf.
Their work concentrates on scheduling requests at a server in the broadcast model. In this model there are different pages of information stored at the server and requests arrive from clients for specific pages in a dynamic and online fashion. When a server broadcasts a page, all clients interested in that page receive it simultaneously. This model is natural and useful in applications such as wireless and LAN networks, and multicast systems.
In the above setting, an important goal is to develop server scheduling algorithms that optimize the Quality of Service that the clients receive. In their work, Moseley and Im study the most popular Quality of Service metrics, namely, average response time.
"Even though broadcast scheduling has been studied extensively over the last decade, the worst-case complexity of the problem is yet to be well understood," said the team. A central question that has been open for almost a decade is whether there is an online scalable algorithm for minimizing average response time. "In this work, we introduce a new algorithm that essentially resolves the question in the affirmative". Although the algorithm is mainly of theoretical interest at this point, the underlying ideas in this work and others done by the team have the potential to be very useful in practice.
Im and Moseley conduct their research work as part of the Algorithms & Theory group, under the guidance of computer science professor Chandra Chekuri. The team focuses on the design and analysis of algorithms and their applications.
The SODA symposium focuses on research topics related to efficient algorithms and data structures for discrete problems. In addition to the design of such methods and structures, the scope also includes their use, performance analysis, and the mathematical problems related to their development or limitations.