File Download

There are no files associated with this item.

  Links for fulltext
     (May Require Subscription)
Supplementary

Conference Paper: A tight analysis of most-requested-first for on-demand data broadcast

TitleA tight analysis of most-requested-first for on-demand data broadcast
Authors
Issue Date2006
PublisherSpringer Verlag. The Journal's web site is located at http://springerlink.com/content/105633/
Citation
The 12th Annual International Conference on Computing and Combinatorics (COCOON 2006), Taipei, Taiwan, 15-18 August 2006. In Lecture Notes In Computer Science, 2006, v. 4112, p. 330-339 How to Cite?
AbstractThis paper gives a complete and tight mathematical analysis on the performance of the Most-Requested-First algorithm for on-demand data broadcast. The algorithm is natural and simple, yet its performance is surprisingly good in practice. We derive tight upper and lower bounds on MRF's competitiveness and thus reveal the exact competitive ratios of the algorithm under different system configurations. We prove that the competitive ratio of MRF is exactly 3 - ℓ/d when the start-up delay d is a multiple of the page length ℓ otherwise the ratio is 3. © Springer-Verlag Berlin Heidelberg 2006.
Persistent Identifierhttp://hdl.handle.net/10722/93178
ISSN
2005 Impact Factor: 0.402
2015 SCImago Journal Rankings: 0.252
References

 

DC FieldValueLanguage
dc.contributor.authorHung, RYSen_HK
dc.contributor.authorTing, HFen_HK
dc.date.accessioned2010-09-25T14:53:15Z-
dc.date.available2010-09-25T14:53:15Z-
dc.date.issued2006en_HK
dc.identifier.citationThe 12th Annual International Conference on Computing and Combinatorics (COCOON 2006), Taipei, Taiwan, 15-18 August 2006. In Lecture Notes In Computer Science, 2006, v. 4112, p. 330-339en_HK
dc.identifier.issn0302-9743-
dc.identifier.urihttp://hdl.handle.net/10722/93178-
dc.description.abstractThis paper gives a complete and tight mathematical analysis on the performance of the Most-Requested-First algorithm for on-demand data broadcast. The algorithm is natural and simple, yet its performance is surprisingly good in practice. We derive tight upper and lower bounds on MRF's competitiveness and thus reveal the exact competitive ratios of the algorithm under different system configurations. We prove that the competitive ratio of MRF is exactly 3 - ℓ/d when the start-up delay d is a multiple of the page length ℓ otherwise the ratio is 3. © Springer-Verlag Berlin Heidelberg 2006.-
dc.languageengen_HK
dc.publisherSpringer Verlag. The Journal's web site is located at http://springerlink.com/content/105633/en_HK
dc.relation.ispartofLecture Notes in Computer Scienceen_HK
dc.titleA tight analysis of most-requested-first for on-demand data broadcasten_HK
dc.typeConference_Paperen_HK
dc.identifier.emailTing, HF: hfting@cs.hku.hken_HK
dc.identifier.authorityTing, HF=rp00177en_HK
dc.description.naturelink_to_subscribed_fulltext-
dc.identifier.scopuseid_2-s2.0-33749582025-
dc.identifier.hkuros123171en_HK
dc.relation.referenceshttp://www.scopus.com/mlt/select.url?eid=2-s2.0-33749582025&selection=ref&src=s&origin=recordpage-
dc.identifier.volume4112-
dc.identifier.spage330en_HK
dc.identifier.epage339en_HK
dc.publisher.placeGermany-
dc.identifier.scopusauthoridHung, RYS=14028462000-
dc.identifier.scopusauthoridTing, HF=7005654198-
dc.customcontrol.immutablesml 160111 - merged-

Export via OAI-PMH Interface in XML Formats


OR


Export to Other Non-XML Formats