Title: Longest Wait First for Broadcast Scheduling [Extended Abstract]
Abstract: 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.
Publication Year: 2010
Publication Date: 2010-01-01
Language: en
Type: book-chapter
Indexed In: ['crossref']
Access and Citation
Cited By Count: 15
AI Researcher Chatbot
Get quick answers to your questions about the article from our AI researcher chatbot