On Broadcast Scheduling

Speaker: Prof. Samir Khuller, University of Maryland
Host: Prof. Leana GolubchikAbstract:
Broadcasting over a wireless channel is a standard mechanism to disseminate information to a set of clients. Clients request different pieces of information, called "pages", and in this "pull-based" model, the server responds with a broadcast schedule. The key property that distinguishes this problem from standard scheduling is that multiple requests may be satisfied by a single broadcast of the requested page. Surprisingly, this small change makes almost all the problems in this area NP-hard whereas without this property these problems can be solved optimally in polynomial time for unit sized pages. This overlap property arises in other contexts as well such as in multi-query processing.We consider a variety of different objective functions in our work minimizing the sum of response times, minimizing the maximum response time and maximizing the number of satisfied requests when requests have deadlines. This is a survey talk based on several papers and will cover a collection of results using a variety of techniques. Finally we propose some open problems. No background knowledge beyond undergraduate algorithms is expected.Biography:
Samir Khuller received his M.S and Ph.D from Cornell University in 1989 and 1990, respectively. He spent two years as a Research Associate at the Institute for Advanced Computer Studies (UMIACS) at the University of Maryland, before joining the Computer Science Department in 1992, where he is currently a Professor in the Department of Computer Science. He spent several summers at the IBM T. J. Watson Research Center, and also visited the IBM Tokyo Research Lab for several weeks. From 2004 to 2008 he was the Associate Chair for Graduate Education.His research interests are in graph algorithms, discrete optimization, and computational geometry. He has published about 140 journal and conference papers, and several book chapters on these topics. He is an editor for the journal Networks, International Journal on Foundations of Computer Science, problems Editor for ACM Trans. on Algorithms, and a columnist for SIGACT News. He has served on several program committees.He received the National Science Foundation's Career Development Award, several Dept. Teaching Awards, the Dean's Teaching Excellence Award and also a CTE-Lilly Teaching Fellowship. In 2003, he and his students were awarded the "Best newcomer paper" award for the ACM PODS Conference. He received the University of Maryland's Distinguished Scholar Teacher Award in 2007, as well as a Google Research Award. He graduated at the top of the Computer Science Class from IIT-Kanpur.

Location: Seaver Science Library (SSL) - 150

Audiences: Everyone Is Invited

Contact: CS Colloquia