File Download

There are no files associated with this item.

  Links for fulltext
     (May Require Subscription)
Supplementary

Conference Paper: Improved on-line broadcast scheduling with deadlines

TitleImproved on-line broadcast scheduling with deadlines
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. 320-329 How to Cite?
AbstractWe study an on-line broadcast scheduling problem in which requests have deadlines, and the objective is to maximize the weighted throughput, i.e., the weighted total length of the satisfied requests. For the case where all requested pages have the same length, we present an online deterministic algorithm named BAR and prove that it is 4.56-competitive. This improves the previous algorithm of Kim and Chwa [11] which is shown to be 5-competitive by Chan et al. [4]. In the case that pages may have different lengths, we prove a lower bound of Ω(Δ/ log Δ) on the competitive ratio where Δ is the ratio of maximum to minimum page lengths. This improves upon the previous √Δ lower bound in [11,4] and is much closer to the current upper bound of (Δ + 2√Δ+2) in [7]. Furthermore, for small values of Δ we give better lower bounds. © Springer-Verlag Berlin Heidelberg 2006.
Persistent Identifierhttp://hdl.handle.net/10722/60617
ISSN
2023 SCImago Journal Rankings: 0.606
References

 

DC FieldValueLanguage
dc.contributor.authorZheng, Fen_HK
dc.contributor.authorFung, SPYen_HK
dc.contributor.authorChan, WTen_HK
dc.contributor.authorChin, FYLen_HK
dc.contributor.authorPoon, CKen_HK
dc.contributor.authorWong, PWHen_HK
dc.date.accessioned2010-05-31T04:15:04Z-
dc.date.available2010-05-31T04:15:04Z-
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. 320-329en_HK
dc.identifier.issn0302-9743en_HK
dc.identifier.urihttp://hdl.handle.net/10722/60617-
dc.description.abstractWe study an on-line broadcast scheduling problem in which requests have deadlines, and the objective is to maximize the weighted throughput, i.e., the weighted total length of the satisfied requests. For the case where all requested pages have the same length, we present an online deterministic algorithm named BAR and prove that it is 4.56-competitive. This improves the previous algorithm of Kim and Chwa [11] which is shown to be 5-competitive by Chan et al. [4]. In the case that pages may have different lengths, we prove a lower bound of Ω(Δ/ log Δ) on the competitive ratio where Δ is the ratio of maximum to minimum page lengths. This improves upon the previous √Δ lower bound in [11,4] and is much closer to the current upper bound of (Δ + 2√Δ+2) in [7]. Furthermore, for small values of Δ we give better lower bounds. © 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.titleImproved on-line broadcast scheduling with deadlinesen_HK
dc.typeConference_Paperen_HK
dc.identifier.openurlhttp://library.hku.hk:4550/resserv?sid=HKU:IR&issn=1094-6136&volume=11&issue=4&spage=299 &epage= 308&date=2008&atitle=Improved+on-line+broadcast+scheduling+with+deadlinesen_HK
dc.identifier.emailChin, FYL:chin@cs.hku.hken_HK
dc.identifier.authorityChin, FYL=rp00105en_HK
dc.description.naturelink_to_subscribed_fulltext-
dc.identifier.scopuseid_2-s2.0-33749579482en_HK
dc.identifier.hkuros128842en_HK
dc.identifier.hkuros154644-
dc.relation.referenceshttp://www.scopus.com/mlt/select.url?eid=2-s2.0-33749579482&selection=ref&src=s&origin=recordpageen_HK
dc.identifier.volume4112en_HK
dc.identifier.spage320en_HK
dc.identifier.epage329en_HK
dc.publisher.placeGermanyen_HK
dc.identifier.scopusauthoridZheng, F=9276481100en_HK
dc.identifier.scopusauthoridFung, SPY=7201970079en_HK
dc.identifier.scopusauthoridChan, WT=7403918060en_HK
dc.identifier.scopusauthoridChin, FYL=7005101915en_HK
dc.identifier.scopusauthoridPoon, CK=7202673523en_HK
dc.identifier.scopusauthoridWong, PWH=9734871500en_HK
dc.customcontrol.immutablesml 151113 - merged-
dc.identifier.issnl0302-9743-

Export via OAI-PMH Interface in XML Formats


OR


Export to Other Non-XML Formats