A note on on-line broadcast scheduling with deadlines |
| |
Authors: | Xin Han He Guo |
| |
Affiliation: | a Department of Computer Science, The University of Hong Kong, Hong Kong b School of Software, Dalian University of Technology, China |
| |
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 an optimal online algorithm, i.e., its competitive ratio matches the lower bound of the problem. |
| |
Keywords: | Online algorithms Broadcast scheduling Competitive ratio |
本文献已被 ScienceDirect 等数据库收录! |
|