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
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?
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
2015 Impact Factor: 0.643
2015 SCImago Journal Rankings: 0.720
ISI Accession Number ID
References

 

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

Export via OAI-PMH Interface in XML Formats


OR


Export to Other Non-XML Formats