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.