File Download

There are no files associated with this item.

  Links for fulltext
     (May Require Subscription)
Supplementary

Article: Competitive analysis of most-request-first for scheduling broadcasts with start-up delay

TitleCompetitive analysis of most-request-first for scheduling broadcasts with start-up delay
Authors
Hung, RYSTing, HF
KeywordsCompetitive analysis
Lower bounds
Non-preemptive scheduling
On-demand data broadcasts
Upper bounds
Issue Date2008
PublisherElsevier BV. The Journal's web site is located at http://www.elsevier.com/locate/tcs
Citation
Theoretical Computer Science, 2008, v. 396 n. 1-3, p. 200-211 How to Cite?
DOI: http://dx.doi.org/10.1016/j.tcs.2008.01.036
AbstractIn this paper, we give a tight and complete mathematical analysis of the Most-Request-First algorithm for scheduling on-demand broadcasts with start-up delay. The algorithm is natural and simple, yet its practical performance is surprisingly good. We derive tight upper and lower bounds on its competitive ratio under different system configurations. Our results reveal an interesting relationship between the start-up delay and the competitiveness of the algorithm. © 2008 Elsevier Ltd. All rights reserved.
Persistent Identifierhttp://hdl.handle.net/10722/88914
ISSN
0304-3975
2023 Impact Factor: 0.9
2023 SCImago Journal Rankings: 0.570
ISI Accession Number ID
WOS:000256199100016
References
References in Scopus

 

DC FieldValueLanguage
dc.contributor.authorHung, RYSen_HK
dc.contributor.authorTing, HFen_HK
dc.date.accessioned2010-09-06T09:50:04Z-
dc.date.available2010-09-06T09:50:04Z-
dc.date.issued2008en_HK
dc.identifier.citationTheoretical Computer Science, 2008, v. 396 n. 1-3, p. 200-211en_HK
dc.identifier.issn0304-3975en_HK
dc.identifier.urihttp://hdl.handle.net/10722/88914-
dc.description.abstractIn this paper, we give a tight and complete mathematical analysis of the Most-Request-First algorithm for scheduling on-demand broadcasts with start-up delay. The algorithm is natural and simple, yet its practical performance is surprisingly good. We derive tight upper and lower bounds on its competitive ratio under different system configurations. Our results reveal an interesting relationship between the start-up delay and the competitiveness of the algorithm. © 2008 Elsevier Ltd. All rights reserved.en_HK
dc.languageengen_HK
dc.publisherElsevier BV. The Journal's web site is located at http://www.elsevier.com/locate/tcsen_HK
dc.relation.ispartofTheoretical Computer Scienceen_HK
dc.rightsTheoretical Computer Science. Copyright © Elsevier BV.en_HK
dc.subjectCompetitive analysisen_HK
dc.subjectLower boundsen_HK
dc.subjectNon-preemptive schedulingen_HK
dc.subjectOn-demand data broadcastsen_HK
dc.subjectUpper boundsen_HK
dc.titleCompetitive analysis of most-request-first for scheduling broadcasts with start-up delayen_HK
dc.typeArticleen_HK
dc.identifier.openurlhttp://library.hku.hk:4550/resserv?sid=HKU:IR&issn=0304-3975&volume=361&issue=1-3&spage=200&epage=&date=2008&atitle=Competitive+analysis+of+most-request-first+for+scheduling+broadcasts+with+start-up+delayen_HK
dc.identifier.emailTing, HF:hfting@cs.hku.hken_HK
dc.identifier.authorityTing, HF=rp00177en_HK
dc.description.naturelink_to_subscribed_fulltext-
dc.identifier.doi10.1016/j.tcs.2008.01.036en_HK
dc.identifier.scopuseid_2-s2.0-42149169630en_HK
dc.identifier.hkuros149512en_HK
dc.relation.referenceshttp://www.scopus.com/mlt/select.url?eid=2-s2.0-42149169630&selection=ref&src=s&origin=recordpageen_HK
dc.identifier.volume396en_HK
dc.identifier.issue1-3en_HK
dc.identifier.spage200en_HK
dc.identifier.epage211en_HK
dc.identifier.isiWOS:000256199100016-
dc.publisher.placeNetherlandsen_HK
dc.identifier.scopusauthoridHung, RYS=14028462000en_HK
dc.identifier.scopusauthoridTing, HF=7005654198en_HK
dc.identifier.issnl0304-3975-

Export via OAI-PMH Interface in XML Formats

OR

Export to Other Non-XML Formats