Indexed by:期刊论文

Date of Publication:2009-01-16

Journal:INFORMATION PROCESSING LETTERS

Included Journals:SCIE、EI、Scopus

Volume:109

Issue:3

Page Number:204-207

ISSN No.: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.