Samir Khuller Colloquium, 11/18
David Kempe
our next theory colloquium speaker will be Prof. Samir Khuller from
the University of Maryland. He just won an award for best teacher
there, so we can look forward to a great talk, I hope. All the
important information is below:
Speaker: Prof. Samir Khuller, University of Maryland
Time: Tuesday, 11/18/2008, 4:00pm
Location: SSL 150
Title: On Broadcast Scheduling
Abstract:
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.
--
David Kempe <dke...@usc.edu>