File Download
There are no files associated with this item.
Links for fulltext
(May Require Subscription)
- Publisher Website: 10.1007/11758471_18
- Scopus: eid_2-s2.0-33746067102
- Find via
Supplementary
-
Citations:
- Scopus: 0
- Appears in Collections:
Conference Paper: A near optimal scheduler for on-demand data broadcasts
Title | A near optimal scheduler for on-demand data broadcasts |
---|---|
Authors | |
Issue Date | 2006 |
Publisher | Springer Verlag. The Journal's web site is located at http://springerlink.com/content/105633/ |
Citation | The 6th Italian Conference on Algorithms and Complexity (CIAC 2006), Rome, Italy, 29-31 May 2006. In Lecture Notes In Computer Science, 2006, v. 3998, p. 163-174 How to Cite? |
Abstract | In an on-demand data broadcast system, clients make requests for data such as weather forecasts, stock prices and traffic information. The server of the system broadcasts the requested data at some time, and all pending requests on this data are satisfied with this single broadcast. All requests have deadlines. The system can abort the current broadcast for more valuable requests and a preempted broadcast may be restarted from the beginning later. In this paper, we design and analyse online scheduler for scheduling broadcasts in such system. The best previously known upper and lower bounds on the competitive ratio of such schedulers are respectively Δ + 2√Δ + 2 and √Δ where Δ is the ratio between the length of the longest and shortest data pages. In this paper, we design a scheduler that has competitive ratio 6Δ/logΔ + O(Δ5/6). We also improve the lower bound of the problem to Δ/2 1n Δ -1, and hence prove that our scheduler is optimal within a constant factor. © Springer-Verlag Berlin Heidelberg 2006. |
Persistent Identifier | http://hdl.handle.net/10722/89046 |
ISSN | 2023 SCImago Journal Rankings: 0.606 |
References |
DC Field | Value | Language |
---|---|---|
dc.contributor.author | Ting, HF | en_HK |
dc.date.accessioned | 2010-09-06T09:51:43Z | - |
dc.date.available | 2010-09-06T09:51:43Z | - |
dc.date.issued | 2006 | en_HK |
dc.identifier.citation | The 6th Italian Conference on Algorithms and Complexity (CIAC 2006), Rome, Italy, 29-31 May 2006. In Lecture Notes In Computer Science, 2006, v. 3998, p. 163-174 | en_HK |
dc.identifier.issn | 0302-9743 | en_HK |
dc.identifier.uri | http://hdl.handle.net/10722/89046 | - |
dc.description.abstract | In an on-demand data broadcast system, clients make requests for data such as weather forecasts, stock prices and traffic information. The server of the system broadcasts the requested data at some time, and all pending requests on this data are satisfied with this single broadcast. All requests have deadlines. The system can abort the current broadcast for more valuable requests and a preempted broadcast may be restarted from the beginning later. In this paper, we design and analyse online scheduler for scheduling broadcasts in such system. The best previously known upper and lower bounds on the competitive ratio of such schedulers are respectively Δ + 2√Δ + 2 and √Δ where Δ is the ratio between the length of the longest and shortest data pages. In this paper, we design a scheduler that has competitive ratio 6Δ/logΔ + O(Δ5/6). We also improve the lower bound of the problem to Δ/2 1n Δ -1, and hence prove that our scheduler is optimal within a constant factor. © Springer-Verlag Berlin Heidelberg 2006. | en_HK |
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.rights | Theoretical Computer Science. Copyright © Elsevier BV. | en_HK |
dc.title | A near optimal scheduler for on-demand data broadcasts | en_HK |
dc.type | Conference_Paper | en_HK |
dc.identifier.openurl | http://library.hku.hk:4550/resserv?sid=HKU:IR&issn=0304-3975&volume=401&issue=1--3&spage=77&epage=&date=2008&atitle=A+Near+Optimal+Scheduler+For+On-demand+Data+Broadcasts | 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.doi | 10.1007/11758471_18 | en_HK |
dc.identifier.scopus | eid_2-s2.0-33746067102 | en_HK |
dc.identifier.hkuros | 123180 | - |
dc.relation.references | http://www.scopus.com/mlt/select.url?eid=2-s2.0-33746067102&selection=ref&src=s&origin=recordpage | en_HK |
dc.identifier.volume | 3998 | en_HK |
dc.identifier.spage | 163 | en_HK |
dc.identifier.epage | 174 | en_HK |
dc.publisher.place | Germany | en_HK |
dc.identifier.scopusauthorid | Ting, HP=7005654198 | en_HK |
dc.customcontrol.immutable | sml 160111 - merged | - |
dc.identifier.issnl | 0302-9743 | - |