File Download
  Links for fulltext
     (May Require Subscription)
Supplementary

Article: A note on on-line broadcast scheduling with deadlines

TitleA note on on-line broadcast scheduling with deadlines
Authors
Han, XGuo, HYin, DZhang, Y
KeywordsBroadcast scheduling
Competitive ratio
Online algorithms
Control theory
Broadcast scheduling
Issue Date2009
PublisherElsevier BV. The Journal's web site is located at http://www.elsevier.com/locate/ipl
Citation
Information Processing Letters, 2009, v. 109 n. 3, p. 204-207 How to Cite?
DOI: http://dx.doi.org/10.1016/j.ipl.2008.10.002
AbstractIn 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.
Persistent Identifierhttp://hub.hku.hk/handle/10722/128787
ISSN
0020-0190
2021 Impact Factor: 0.851
2020 SCImago Journal Rankings: 0.415
ISI Accession Number ID
WOS:000262560900008

 

DC FieldValueLanguage
dc.contributor.authorHan, X-
dc.contributor.authorGuo, H-
dc.contributor.authorYin, D-
dc.contributor.authorZhang, Y-
dc.date.accessioned2010-11-23T06:36:45Z-
dc.date.available2010-11-23T06:36:45Z-
dc.date.issued2009-
dc.identifier.citationInformation Processing Letters, 2009, v. 109 n. 3, p. 204-207-
dc.identifier.issn0020-0190-
dc.identifier.urihttp://hub.hku.hk/handle/10722/128787-
dc.description.abstractIn 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.-
dc.languageeng-
dc.publisherElsevier BV. The Journal's web site is located at http://www.elsevier.com/locate/ipl-
dc.relation.ispartofInformation Processing Letters-
dc.rightsThis work is licensed under a Creative Commons Attribution-NonCommercial-NoDerivatives 4.0 International License.-
dc.subjectBroadcast scheduling-
dc.subjectCompetitive ratio-
dc.subjectOnline algorithms-
dc.subjectControl theory-
dc.subjectBroadcast scheduling-
dc.titleA note on on-line broadcast scheduling with deadlinesen_HK
dc.typeArticleen_HK
dc.identifier.openurlhttp://library.hku.hk:4550/resserv?sid=HKU:IR&issn=0020-0190&volume=109&issue=3&spage=204&epage=207&date=2009&atitle=A+note+on+on-line+broadcast+scheduling+with+deadlines-
dc.identifier.emailHan, X: :xhan@cs.hku.hk-
dc.identifier.emailGuo, H: guohe@dlut.edu.cn-
dc.identifier.emailYin, D: dwyin@cs.hku.hk-
dc.identifier.emailZhang, Y: yzhang@cs.hku.hk, yzhang.hku@gmail.com-
dc.description.naturepostprint-
dc.identifier.doi10.1016/j.ipl.2008.10.002-
dc.identifier.scopuseid_2-s2.0-57349153080-
dc.identifier.hkuros164458-
dc.identifier.volume109-
dc.identifier.issue3-
dc.identifier.spage204-
dc.identifier.epage207-
dc.identifier.isiWOS:000262560900008-
dc.identifier.issnl0020-0190-

Export via OAI-PMH Interface in XML Formats

OR

Export to Other Non-XML Formats