Better scalable algorithms for broadcast scheduling

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 the average flowtime of the requests. In this paper, for any e>¿0, we give a (1¿+¿e)-speed O(1/e ^3)-competitive online algorithm for the broadcast scheduling problem, even when page sizes are not identical. This improves over the recent breakthrough result of Im and Moseley [18], where they obtained a (1¿+¿e)-speed O(1/e ^11)-competitive algorithm for the setting when all pages have the same size. This is the first scalable algorithm for broadcast scheduling with varying size pages, and resolves the main open question from [18]. Furthermore, our algorithm and analysis are considerably simpler than [18], and also extend to the general setting of dependent requests