Approximation Algorithms for Broadcast Scheduling
Nikhil Bansal
IBM T. J. Watson Research Center
Friday, September 29th, 2006, 3:30 pm
Wean Hall 7220
Abstract
We consider the following problem in the broadcast scheduling model. There are n pages at a broadcast server, and at each time slot the server receives several requests for these pages. The server can transmit exactly one page per time slot, and once a page is transmitted, it satisfies all the requests waiting for that page. The goal is to find a broadcast schedule that minimizes the average waiting time of requests.
I will describe a poly-logarithmic approximation ratio for this problem, that improves upon the previously known bound of O(n^{1/2}).
This is joint work with Don Coppersmith and Maxim Sviridenko.
