Indexed by:Journal Article

Date of Publication:2009-01-16

Journal:INFORMATION PROCESSING LETTERS

Included Journals:Scopus、EI、SCIE

Volume:109

Issue:3

Page Number:204-207

ISSN:0020-0190

Key Words:Online algorithms; Broadcast scheduling; Competitive ratio

Abstract: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.