File Download

There are no files associated with this item.

  Links for fulltext
     (May Require Subscription)
Supplementary

Article: A near optimal scheduler for on-demand data broadcasts

TitleA near optimal scheduler for on-demand data broadcasts
Authors
Ting, HF
KeywordsCompetitive Ratios
Lower Bounds
On-Demand Data Broadcasting
Online Algorithms
Scheduling
Issue Date2008
PublisherElsevier BV. The Journal's web site is located at http://www.elsevier.com/locate/tcs
Citation
Theoretical Computer Science, 2008, v. 401 n. 1-3, p. 77-84 How to Cite?
DOI: http://dx.doi.org/10.1016/j.tcs.2008.03.031
AbstractOn-demand data broadcasting is a new and important technique for information dissemination. In this paper, we design and analyse a novel online scheduler Balance for scheduling on-demand data broadcasts. Balance has competitive ratio frac(6 Δ, log Δ) + O (Δ5 / 6), which improves significantly the previous best upper bound of Δ + sqrt(Δ) + 2. We also prove that any online scheduler for the problem cannot have competitive ratio smaller than frac(Δ, 2 ln Δ) - 1. It follows that Balance is optimal within a constant factor. © 2008 Elsevier B.V. All rights reserved.
Persistent Identifierhttp://hdl.handle.net/10722/152389
ISSN
0304-3975
2023 Impact Factor: 0.9
2023 SCImago Journal Rankings: 0.570
ISI Accession Number ID
WOS:000258203300007
References
References in Scopus

 

DC FieldValueLanguage
dc.contributor.authorTing, HFen_US
dc.date.accessioned2012-06-26T06:37:52Z-
dc.date.available2012-06-26T06:37:52Z-
dc.date.issued2008en_US
dc.identifier.citationTheoretical Computer Science, 2008, v. 401 n. 1-3, p. 77-84en_US
dc.identifier.issn0304-3975en_US
dc.identifier.urihttp://hdl.handle.net/10722/152389-
dc.description.abstractOn-demand data broadcasting is a new and important technique for information dissemination. In this paper, we design and analyse a novel online scheduler Balance for scheduling on-demand data broadcasts. Balance has competitive ratio frac(6 Δ, log Δ) + O (Δ5 / 6), which improves significantly the previous best upper bound of Δ + sqrt(Δ) + 2. We also prove that any online scheduler for the problem cannot have competitive ratio smaller than frac(Δ, 2 ln Δ) - 1. It follows that Balance is optimal within a constant factor. © 2008 Elsevier B.V. All rights reserved.en_US
dc.languageengen_US
dc.publisherElsevier BV. The Journal's web site is located at http://www.elsevier.com/locate/tcsen_US
dc.relation.ispartofTheoretical Computer Scienceen_US
dc.subjectCompetitive Ratiosen_US
dc.subjectLower Boundsen_US
dc.subjectOn-Demand Data Broadcastingen_US
dc.subjectOnline Algorithmsen_US
dc.subjectSchedulingen_US
dc.titleA near optimal scheduler for on-demand data broadcastsen_US
dc.typeArticleen_US
dc.identifier.emailTing, HF:hfting@cs.hku.hken_US
dc.identifier.authorityTing, HF=rp00177en_US
dc.description.naturelink_to_subscribed_fulltexten_US
dc.identifier.doi10.1016/j.tcs.2008.03.031en_US
dc.identifier.scopuseid_2-s2.0-45049088071en_US
dc.identifier.hkuros149511-
dc.relation.referenceshttp://www.scopus.com/mlt/select.url?eid=2-s2.0-45049088071&selection=ref&src=s&origin=recordpageen_US
dc.identifier.volume401en_US
dc.identifier.issue1-3en_US
dc.identifier.spage77en_US
dc.identifier.epage84en_US
dc.identifier.isiWOS:000258203300007-
dc.publisher.placeNetherlandsen_US
dc.identifier.scopusauthoridTing, HF=7005654198en_US
dc.identifier.issnl0304-3975-

Export via OAI-PMH Interface in XML Formats

OR

Export to Other Non-XML Formats