Longest wait first for broadcast scheduling

Chandra Sekhar Chekuri, Sungjin Im, Benjamin Moseley

Research output: Chapter in Book/Report/Conference proceedingConference contribution

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. - We give an intuitive and easy to understand analysis of LWF which shows that it is O(1/ε2)-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.

Original languageEnglish (US)
Title of host publicationApproximation and Online Algorithms - 7th International Workshop, WAOA 2009, Revised Papers
Pages62-74
Number of pages13
DOIs
StatePublished - Dec 1 2009
Event7th Workshop on Approximation and Online Algorithms, WAOA 2009 - Copenhagen, Denmark
Duration: Sep 10 2009Sep 11 2009

Publication series

NameLecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)
Volume5893 LNCS
ISSN (Print)0302-9743
ISSN (Electronic)1611-3349

Other

Other7th Workshop on Approximation and Online Algorithms, WAOA 2009
CountryDenmark
CityCopenhagen
Period9/10/099/11/09

ASJC Scopus subject areas

  • Theoretical Computer Science
  • Computer Science(all)

Fingerprint Dive into the research topics of 'Longest wait first for broadcast scheduling'. Together they form a unique fingerprint.

Cite this