Online Algorithms for Broadcast Scheduling
March 2, 2011
ABSTRACT:
In the classic broadcast scheduling problem, there are n pages (of unit size) stored at a server, and requests for
these pages arrive over time. Whenever a page is broadcast, it satisfies all outstanding requests
for that page. The objective is to minimize average flowtime of the requests.
In this talk, we will present a (1+eps )-speed O(1/eps^3)-competitive online algorithm for any arbitrary eps>0. The algorithm will first produce a good "fractional schedule", and then subsequently round this to get a good integral broadcast sequence, and these steps are done online. The notion of resource augmentation is the following: in any time interval of length 1/eps, our online algorithm can broadcast 1/eps+1 pages while the optimal algorithm can only broadcast 1/eps pages.
This is joint work with Nikhil Bansal and Viswanath Nagarajan.
In this talk, we will present a (1+eps )-speed O(1/eps^3)-competitive online algorithm for any arbitrary eps>0. The algorithm will first produce a good "fractional schedule", and then subsequently round this to get a good integral broadcast sequence, and these steps are done online. The notion of resource augmentation is the following: in any time interval of length 1/eps, our online algorithm can broadcast 1/eps+1 pages while the optimal algorithm can only broadcast 1/eps pages.
This is joint work with Nikhil Bansal and Viswanath Nagarajan.