File Download
There are no files associated with this item.
Supplementary
-
Citations:
- Scopus: 0
- Appears in Collections:
Conference Paper: A tight analysis of most-requested-first for on-demand data broadcast
Title | A tight analysis of most-requested-first for on-demand data broadcast |
---|---|
Authors | |
Issue Date | 2006 |
Publisher | Springer 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? |
Abstract | This 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 Identifier | http://hdl.handle.net/10722/93178 |
ISSN | 2023 SCImago Journal Rankings: 0.606 |
References |
DC Field | Value | Language |
---|---|---|
dc.contributor.author | Hung, RYS | en_HK |
dc.contributor.author | Ting, HF | en_HK |
dc.date.accessioned | 2010-09-25T14:53:15Z | - |
dc.date.available | 2010-09-25T14:53:15Z | - |
dc.date.issued | 2006 | en_HK |
dc.identifier.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 | en_HK |
dc.identifier.issn | 0302-9743 | - |
dc.identifier.uri | http://hdl.handle.net/10722/93178 | - |
dc.description.abstract | This 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.language | eng | en_HK |
dc.publisher | Springer Verlag. The Journal's web site is located at http://springerlink.com/content/105633/ | en_HK |
dc.relation.ispartof | Lecture Notes in Computer Science | en_HK |
dc.title | A tight analysis of most-requested-first for on-demand data broadcast | en_HK |
dc.type | Conference_Paper | en_HK |
dc.identifier.email | Ting, HF: hfting@cs.hku.hk | en_HK |
dc.identifier.authority | Ting, HF=rp00177 | en_HK |
dc.description.nature | link_to_subscribed_fulltext | - |
dc.identifier.scopus | eid_2-s2.0-33749582025 | - |
dc.identifier.hkuros | 123171 | en_HK |
dc.relation.references | http://www.scopus.com/mlt/select.url?eid=2-s2.0-33749582025&selection=ref&src=s&origin=recordpage | - |
dc.identifier.volume | 4112 | - |
dc.identifier.spage | 330 | en_HK |
dc.identifier.epage | 339 | en_HK |
dc.publisher.place | Germany | - |
dc.identifier.scopusauthorid | Hung, RYS=14028462000 | - |
dc.identifier.scopusauthorid | Ting, HF=7005654198 | - |
dc.customcontrol.immutable | sml 160111 - merged | - |
dc.identifier.issnl | 0302-9743 | - |