A note on on-line broadcast scheduling with deadlines

被引：0
作者：
Han, Xin [1 ]
Guo, He [2 ]
Yin, Dawei [1 ]
Zhang, Yong [1 ]
机构：
[1] Univ Hong Kong, Dept Comp Sci, Hong Kong, Hong Kong, Peoples R China
[2] Dalian Univ Technol, Sch Software, Dalian, Peoples R China
来源：
INFORMATION PROCESSING LETTERS | 2009年 / 109卷 / 03期
关键词：
Online algorithms; Broadcast scheduling; Competitive ratio;
D O I：
10.1016/j.ipl.2008.10.002
中图分类号：
TP [自动化技术、计算机技术];
学科分类号：
0812 ;
摘要：
In this paper, we Study an on-line broadcast scheduling problem with deadlines, in which the requests asking for the same page can be satisfied Simultaneously by broadcasting this page, and every request is associated with a release time, deadline and a required page with a unit size. The objective is to maximize the number of requests satisfied by the schedule. In this paper, we focus on an important special case where all the requests have their spans (the difference between release time and deadline) less than 2. We give in optimal online algorithm, i.e.. its competitive ratio matches the lower bound of the problem. (C) 2008 Elsevier B.V. All rights reserved.
引用
收藏
页码：204 / 207
页数：4
相关论文
共 13 条
[1]  
BANSAL N, 2005, SODA 05, P215
[2]  
BANSAL N, SODA 2006, P344
[3]  
BARTAL Y, SODA 2000, P558
[4]  
CHAN W, COCOON 2004, P210
[5]  
CHANG J, SODA 2008
[6]   Multicast pull scheduling: When fairness is fine [J].
Edmonds, J ;
Pruhs, K .
ALGORITHMICA, 2003, 36 (03) :315-330
[7]   Scheduling in the dark [J].
Edmonds, J .
THEORETICAL COMPUTER SCIENCE, 2000, 235 (01) :109-141
[8]   A Maiden Analysis of Longest Wait First [J].
Edmonds, Jeff ;
Pruhs, Kirk .
ACM TRANSACTIONS ON ALGORITHMS, 2005, 1 (01) :14-32
[9]  
FUNG SPY, 2005, P 11 IT C THEOR COMP, P251
[10]   Improved on-line broadcast scheduling with deadlines [J].
Fung, Stanley P. Y. ;
Zheng, Feifeng ;
Chan, Wun-Tat ;
Chin, Francis Y. L. ;
Poon, Chung Keung ;
Wong, Prudence W. H. .
JOURNAL OF SCHEDULING, 2008, 11 (04) :299-308
12