CMU-CS-09-174
Computer Science Department
School of Computer Science, Carnegie Mellon University



CMU-CS-09-174

Better Scalable Algorithms for Broadcast Scheduling

Nikhil Bansal*, Ravishankar Krishnaswamy, Viswanath Nagarajan*

November 2009

CMU-CS-09-174.ps
CMU-CS-09-174.pdf


Keywords: Broadcast scheduling, online algorithms

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].

29 pages

*IBM T.J. Watson Research Center


Return to: SCS Technical Report Collection
School of Computer Science

This page maintained by reports@cs.cmu.edu