Improved on-line broadcast scheduling with deadlines |
| |
Authors: | Stanley P Y Fung Feifeng Zheng Wun-Tat Chan Francis Y L Chin Chung Keung Poon Prudence W H Wong |
| |
Affiliation: | (1) Department of Computer Science, University of Leicester, Leicester, UK;(2) School of Management, Xi’an JiaoTong University, Xi’an, China;(3) Department of Computer Science, The University of Hong Kong, Hong Kong, Hong Kong;(4) Department of Computer Science, City University of Hong Kong, Hong Kong, Hong Kong;(5) Department of Computer Science, University of Liverpool, Liverpool, UK |
| |
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 (
)-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.
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]. |
| |
Keywords: | Online algorithms Broadcast scheduling Competitive analysis |
本文献已被 SpringerLink 等数据库收录! |
|