点击次数：

论文类型：期刊论文

发表时间：2009-01-16

发表刊物：INFORMATION PROCESSING LETTERS

收录刊物：SCIE、EI、Scopus

卷号：109

期号：3

页面范围：204-207

ISSN号：0020-0190

关键字：Online algorithms; Broadcast scheduling; Competitive ratio

摘要：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.