Improved on-line broadcast scheduling with deadlines

Research output: Journal Publications and Reviews (RGC: 21, 22, 62)21_Publication in refereed journalNot applicablepeer-review

9 Scopus Citations
View graph of relations

Author(s)

  • Stanley P. Y. Fung
  • Feifeng Zheng
  • Wun-Tat Chan
  • Francis Y. L. Chin
  • Chung Keung Poon
  • And 1 others
  • Prudence W. H. Wong

Related Research Unit(s)

Detail(s)

Original languageEnglish
Pages (from-to)299-308
Journal / PublicationJournal of Scheduling
Volume11
Issue number4
Publication statusPublished - Aug 2008

Abstract

We study an on-line broadcast scheduling problem in which requests have deadlines, and the objective is to maximize the weighted throughput, i.e., the weighted total length of the satisfied requests. For the case where all requested pages have the same length, we present an online deterministic algorithm named BAR and prove that it is 4.56-competitive. This improves the previous algorithm of (Kim, J.-H., Chwa, K.-Y. in Theor. Comput. Sci. 325(3):479-488, 2004) which is shown to be 5-competitive by (Chan, W.-T., et al. in Lecture Notes in Computer Science, vol. 3106, pp. 210-218, 2004). In the case that pages may have different lengths, we give a (Δ + 2√Δ + 2)-competitive algorithm where Δ is the ratio of maximum to minimum page lengths. This improves the (4Δ+3)-competitive algorithm of (Chan, W.-T., et al. in Lecture Notes in Computer Science, vol. 3106, pp. 210-218, 2004). We also prove an almost matching lower bound of Ω(Δ/ log∈Δ). Furthermore, for small values of Δ we give better lower bounds. © 2007 Springer Science+Business Media, LLC.

Research Area(s)

  • Broadcast scheduling, Competitive analysis, Online algorithms

Citation Format(s)

Improved on-line broadcast scheduling with deadlines. / Fung, Stanley P. Y.; Zheng, Feifeng; Chan, Wun-Tat; Chin, Francis Y. L.; Poon, Chung Keung; Wong, Prudence W. H.

In: Journal of Scheduling, Vol. 11, No. 4, 08.2008, p. 299-308.

Research output: Journal Publications and Reviews (RGC: 21, 22, 62)21_Publication in refereed journalNot applicablepeer-review