Minimizing maximum response time and delay factor in broadcast scheduling

Chandra Chekuri, Sungjin Im, Benjamin Moseley

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

Abstract

We consider online algorithms for pull-based broadcast scheduling. In this setting there are n pages of information at a server and requests for pages arrive online. When the server serves (broadcasts) a page p, all outstanding requests for that page are satisfied. We study two related metrics, namely maximum response time (waiting time) and maximum delay-factor and their weighted versions. We obtain the following results in the worst-case online competitive model. We show that FIFO (first-in first-out) is 2-competitive even when the page sizes are different. Previously this was known only for unit-sized pages [10] via a delicate argument. Our proof differs from [10] and is perhaps more intuitive. We give an online algorithm for maximum delay-factor that is O(1/ε 2)-competitive with (1+ε)-speed for unit-sized pages and with (2+ε)-speed for different sized pages. This improves on the algorithm in [13] which required (2+ε)-speed and (4+ε)-speed respectively. In addition we show that the algorithm and analysis can be extended to obtain the same results for maximum weighted response time and delay factor. We show that a natural greedy algorithm modeled after LWF (Longest-Wait-First) is not O(1)-competitive for maximum delay factor with any constant speed even in the setting of standard scheduling with unit-sized jobs. This complements our upper bound and demonstrates the importance of the tradeoff made in our algorithm.

Original languageEnglish (US)
Title of host publicationAlgorithms - ESA 2009 - 17th Annual European Symposium, Proceedings
Pages444-455
Number of pages12
DOIs
StatePublished - Nov 2 2009
Event17th Annual European Symposium on Algorithms, ESA 2009 - Copenhagen, Denmark
Duration: Sep 7 2009Sep 9 2009

Publication series

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

Other

Other17th Annual European Symposium on Algorithms, ESA 2009
CountryDenmark
CityCopenhagen
Period9/7/099/9/09

ASJC Scopus subject areas

  • Theoretical Computer Science
  • Computer Science(all)

Fingerprint Dive into the research topics of 'Minimizing maximum response time and delay factor in broadcast scheduling'. Together they form a unique fingerprint.

  • Cite this

    Chekuri, C., Im, S., & Moseley, B. (2009). Minimizing maximum response time and delay factor in broadcast scheduling. In Algorithms - ESA 2009 - 17th Annual European Symposium, Proceedings (pp. 444-455). (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics); Vol. 5757 LNCS). https://doi.org/10.1007/978-3-642-04128-0_40