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/ξ³)-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/ξ¹¹)-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