Computer Science Department
School of Computer Science, Carnegie Mellon University
Better Scalable Algorithms for Broadcast Scheduling
Nikhil Bansal*, Ravishankar Krishnaswamy, Viswanath Nagarajan*
In the classic broadcast scheduling problem, there are n pages 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. For any ξ > 0, we give a (1+ ξ)-speed O(1/ξ3)-competitive online algorithm for broadcast scheduling. This improves over the recent breakthrough result of Im and Moseley [IM10], where they obtained a (1+ξ)-speed O(1/ξ11)-competitive algorithm. Our algorithm and analysis are considerably simpler than [IM10]. More importantly, our techniques also extend to the general setting of non-uniform page-sizes and dependent-requests. This is the first scalable algorithm for broadcast scheduling with varying size pages, and resolves the main open question from [IM10].
*IBM T.J. Watson Research Center