Longest wait first for broadcast scheduling

We consider online algorithms for broadcast scheduling. In the pull-based broadcast model there are n unit-sized pages of information at a server and requests arrive online for pages. When the server transmits a page p, all outstanding requests for that page are satisfied. There is a lower bound of Ω(n) on the competitiveness of online algorithms to minimize average flow-time; therefore we consider resource augmentation analysis in which the online algorithm is given extra speed over the adversary. The longest-wait-first (LWF) algorithm is a natural algorithm that has been shown to have good empirical performance [2]. Edmonds and Pruhs showed that LWF is 6-speed O(1)-competitive using a novel yet complex analysis; they also showed that LWF is not O(1)-competitive with less than 1.618-speed. In this paper we make two main contributions to the analysis of LWF and broadcast scheduling. - We give an intuitive and easy to understand analysis of LWF which shows that it is O(1/ε²)-competitive for average flow-time with (4+ε) speed. - We show that a natural extension of LWF is O(1)-speed O(1)-competitive for more general objective functions such as average delay-factor and L _κ norms of delay-factor (for fixed κ). These metrics generalize average flow-time and L_κ norms of flow-time respectively and ours are the first non-trivial results for these objective functions in broadcast scheduling.