Improved On-Line Broadcast Scheduling with Deadlines

Feifeng Zheng; Stanley P.Y. Fung; Wun Tat Chan; Francis Y.L. Chin; Chung Keung Poon; Prudence W.H. Wong

doi:10.1007/11809678_34

Improved On-Line Broadcast Scheduling with Deadlines

Feifeng Zheng
, Stanley P.Y. Fung
, Wun Tat Chan
, Francis Y.L. Chin
, Chung Keung Poon
, Prudence W.H. Wong

School of Continuing Education

Research output: Chapter in book/report/conference proceeding › Conference proceeding › peer-review

25 Citations (Scopus)

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 and Chwa [11] which is shown to be 5-competitive by Chan et al. [4]. In the case that pages may have different lengths, we prove a lower bound of Ω(Δ/ log Δ) on the competitive ratio where Δ is the ratio of maximum to minimum page lengths. This improves upon the previous √Δ lower bound in [11,4] and is much closer to the current upper bound of (Δ + 2√Δ+2) in [7]. Furthermore, for small values of Δ we give better lower bounds.

Original language	English
Title of host publication	Computing and Combinatorics
Subtitle of host publication	12th Annual International Conference, COCOON 2006, Taipei, Taiwan, August 15-18, 2006, Proceedings
Editors	Danny Z. Chen, D. T. Lee
Place of Publication	Heidelberg
Publisher	Springer Berlin Heidelberg
Pages	320-329
Number of pages	10
Edition	1st
ISBN (Electronic)	9783540369264
ISBN (Print)	3540369252, 9783540369257
DOIs	https://doi.org/10.1007/11809678_34
Publication status	Published - 31 Jul 2006
Event	12th Annual International Conference on Computing and Combinatorics, COCOON 2006 - Taipei, Taiwan, China Duration: 15 Aug 2006 → 18 Aug 2006

Publication series

Name	Lecture Notes in Computer Science
Volume	4112
ISSN (Print)	0302-9743
ISSN (Electronic)	1611-3349

Name	Theoretical Computer Science and General Issues
ISSN (Print)	2512-2010
ISSN (Electronic)	2512-2029

Name	COCOON: International Computing and Combinatorics Conference

Conference

Conference	12th Annual International Conference on Computing and Combinatorics, COCOON 2006
Country/Territory	Taiwan, China
City	Taipei
Period	15/08/06 → 18/08/06

UN SDGs

This output contributes to the following UN Sustainable Development Goals (SDGs)

SDG 9 Industry, Innovation, and Infrastructure

User-Defined Keywords

Competitive Ratio
Broadcast Schedule
Data Broadcast
Idle Interval
Tight Deadline

Access to Document

10.1007/11809678_34

Cite this

Zheng, F., Fung, S. P. Y., Chan, W. T., Chin, F. Y. L., Poon, C. K., & Wong, P. W. H. (2006). Improved On-Line Broadcast Scheduling with Deadlines. In D. Z. Chen, & D. T. Lee (Eds.), Computing and Combinatorics: 12th Annual International Conference, COCOON 2006, Taipei, Taiwan, August 15-18, 2006, Proceedings (1st ed., pp. 320-329). (Lecture Notes in Computer Science; Vol. 4112), (Theoretical Computer Science and General Issues), (COCOON: International Computing and Combinatorics Conference). Springer Berlin Heidelberg. https://doi.org/10.1007/11809678_34

Zheng, Feifeng ; Fung, Stanley P.Y. ; Chan, Wun Tat et al. / Improved On-Line Broadcast Scheduling with Deadlines. Computing and Combinatorics: 12th Annual International Conference, COCOON 2006, Taipei, Taiwan, August 15-18, 2006, Proceedings. editor / Danny Z. Chen ; D. T. Lee. 1st. ed. Heidelberg : Springer Berlin Heidelberg, 2006. pp. 320-329 (Lecture Notes in Computer Science). (Theoretical Computer Science and General Issues). (COCOON: International Computing and Combinatorics Conference).

@inproceedings{1ffb8d3cdf0b4e4cbe27f9d77b7cf5fc,

title = "Improved On-Line Broadcast Scheduling with Deadlines",

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 and Chwa [11] which is shown to be 5-competitive by Chan et al. [4]. In the case that pages may have different lengths, we prove a lower bound of Ω(Δ/ log Δ) on the competitive ratio where Δ is the ratio of maximum to minimum page lengths. This improves upon the previous √Δ lower bound in [11,4] and is much closer to the current upper bound of (Δ + 2√Δ+2) in [7]. Furthermore, for small values of Δ we give better lower bounds.",

keywords = "Competitive Ratio, Broadcast Schedule, Data Broadcast, Idle Interval, Tight Deadline",

author = "Feifeng Zheng and Fung, \{Stanley P.Y.\} and Chan, \{Wun Tat\} and Chin, \{Francis Y.L.\} and Poon, \{Chung Keung\} and Wong, \{Prudence W.H.\}",

note = "The work described in this paper was fully supported by grants from the Research Grants Council of the Hong Kong SAR, China [CityU 1198/03E, HKU 7142/03E, HKU 5172/03E], an NSF Grant of China [No. 10371094], and a Nuffield Foundation Grant of UK [NAL/01004/G]. Publisher copyright: {\textcopyright} 2006 Springer-Verlag Berlin Heidelberg; 12th Annual International Conference on Computing and Combinatorics, COCOON 2006 ; Conference date: 15-08-2006 Through 18-08-2006",

year = "2006",

month = jul,

day = "31",

doi = "10.1007/11809678\_34",

language = "English",

isbn = "3540369252",

series = "Lecture Notes in Computer Science",

publisher = "Springer Berlin Heidelberg",

pages = "320--329",

editor = "Chen, \{Danny Z.\} and Lee, \{D. T.\}",

booktitle = "Computing and Combinatorics",

edition = "1st",

}

Zheng, F, Fung, SPY, Chan, WT, Chin, FYL, Poon, CK & Wong, PWH 2006, Improved On-Line Broadcast Scheduling with Deadlines. in DZ Chen & DT Lee (eds), Computing and Combinatorics: 12th Annual International Conference, COCOON 2006, Taipei, Taiwan, August 15-18, 2006, Proceedings. 1st edn, Lecture Notes in Computer Science, vol. 4112, Theoretical Computer Science and General Issues, COCOON: International Computing and Combinatorics Conference, Springer Berlin Heidelberg, Heidelberg, pp. 320-329, 12th Annual International Conference on Computing and Combinatorics, COCOON 2006, Taipei, Taiwan, China, 15/08/06. https://doi.org/10.1007/11809678_34

Improved On-Line Broadcast Scheduling with Deadlines. / Zheng, Feifeng; Fung, Stanley P.Y.; Chan, Wun Tat et al.
Computing and Combinatorics: 12th Annual International Conference, COCOON 2006, Taipei, Taiwan, August 15-18, 2006, Proceedings. ed. / Danny Z. Chen; D. T. Lee. 1st. ed. Heidelberg: Springer Berlin Heidelberg, 2006. p. 320-329 (Lecture Notes in Computer Science; Vol. 4112), (Theoretical Computer Science and General Issues), (COCOON: International Computing and Combinatorics Conference).

Research output: Chapter in book/report/conference proceeding › Conference proceeding › peer-review

TY - GEN

T1 - Improved On-Line Broadcast Scheduling with Deadlines

AU - Zheng, Feifeng

AU - Fung, Stanley P.Y.

AU - Chan, Wun Tat

AU - Chin, Francis Y.L.

AU - Poon, Chung Keung

AU - Wong, Prudence W.H.

N1 - The work described in this paper was fully supported by grants from the Research Grants Council of the Hong Kong SAR, China [CityU 1198/03E, HKU 7142/03E, HKU 5172/03E], an NSF Grant of China [No. 10371094], and a Nuffield Foundation Grant of UK [NAL/01004/G]. Publisher copyright: © 2006 Springer-Verlag Berlin Heidelberg

PY - 2006/7/31

Y1 - 2006/7/31

N2 - 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 and Chwa [11] which is shown to be 5-competitive by Chan et al. [4]. In the case that pages may have different lengths, we prove a lower bound of Ω(Δ/ log Δ) on the competitive ratio where Δ is the ratio of maximum to minimum page lengths. This improves upon the previous √Δ lower bound in [11,4] and is much closer to the current upper bound of (Δ + 2√Δ+2) in [7]. Furthermore, for small values of Δ we give better lower bounds.

AB - 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 and Chwa [11] which is shown to be 5-competitive by Chan et al. [4]. In the case that pages may have different lengths, we prove a lower bound of Ω(Δ/ log Δ) on the competitive ratio where Δ is the ratio of maximum to minimum page lengths. This improves upon the previous √Δ lower bound in [11,4] and is much closer to the current upper bound of (Δ + 2√Δ+2) in [7]. Furthermore, for small values of Δ we give better lower bounds.

KW - Competitive Ratio

KW - Broadcast Schedule

KW - Data Broadcast

KW - Idle Interval

KW - Tight Deadline

UR - https://www.scopus.com/pages/publications/33749579482

U2 - 10.1007/11809678_34

DO - 10.1007/11809678_34

M3 - Conference proceeding

AN - SCOPUS:33749579482

SN - 3540369252

SN - 9783540369257

T3 - Lecture Notes in Computer Science

SP - 320

EP - 329

BT - Computing and Combinatorics

A2 - Chen, Danny Z.

A2 - Lee, D. T.

PB - Springer Berlin Heidelberg

CY - Heidelberg

T2 - 12th Annual International Conference on Computing and Combinatorics, COCOON 2006

Y2 - 15 August 2006 through 18 August 2006

ER -

Zheng F, Fung SPY, Chan WT, Chin FYL, Poon CK, Wong PWH. Improved On-Line Broadcast Scheduling with Deadlines. In Chen DZ, Lee DT, editors, Computing and Combinatorics: 12th Annual International Conference, COCOON 2006, Taipei, Taiwan, August 15-18, 2006, Proceedings. 1st ed. Heidelberg: Springer Berlin Heidelberg. 2006. p. 320-329. (Lecture Notes in Computer Science). (Theoretical Computer Science and General Issues). (COCOON: International Computing and Combinatorics Conference). doi: 10.1007/11809678_34

Improved On-Line Broadcast Scheduling with Deadlines

Abstract

Publication series

Conference

UN SDGs

User-Defined Keywords

Access to Document

Other files and links

Fingerprint

Cite this