File Download

There are no files associated with this item.

  Links for fulltext
     (May Require Subscription)
Supplementary

Conference Paper: A near optimal scheduler for on-demand data broadcasts

TitleA near optimal scheduler for on-demand data broadcasts
Authors
Issue Date2006
PublisherSpringer 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?
AbstractIn 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 Identifierhttp://hdl.handle.net/10722/89046
ISSN
2005 Impact Factor: 0.402
2015 SCImago Journal Rankings: 0.252
References

 

DC FieldValueLanguage
dc.contributor.authorTing, HFen_HK
dc.date.accessioned2010-09-06T09:51:43Z-
dc.date.available2010-09-06T09:51:43Z-
dc.date.issued2006en_HK
dc.identifier.citationThe 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-174en_HK
dc.identifier.issn0302-9743en_HK
dc.identifier.urihttp://hdl.handle.net/10722/89046-
dc.description.abstractIn 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.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.rightsTheoretical Computer Science. Copyright © Elsevier BV.en_HK
dc.titleA near optimal scheduler for on-demand data broadcastsen_HK
dc.typeConference_Paperen_HK
dc.identifier.openurlhttp://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+Broadcastsen_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.1007/11758471_18en_HK
dc.identifier.scopuseid_2-s2.0-33746067102en_HK
dc.identifier.hkuros123180-
dc.relation.referenceshttp://www.scopus.com/mlt/select.url?eid=2-s2.0-33746067102&selection=ref&src=s&origin=recordpageen_HK
dc.identifier.volume3998en_HK
dc.identifier.spage163en_HK
dc.identifier.epage174en_HK
dc.publisher.placeGermanyen_HK
dc.identifier.scopusauthoridTing, HP=7005654198en_HK
dc.customcontrol.immutablesml 160111 - merged-

Export via OAI-PMH Interface in XML Formats


OR


Export to Other Non-XML Formats