File Download

There are no files associated with this item.

  Links for fulltext
     (May Require Subscription)
Supplementary

Article: Improved on-line broadcast scheduling with deadlines

TitleImproved on-line broadcast scheduling with deadlines
Authors
KeywordsBroadcast Scheduling
Competitive Analysis
Online Algorithms
Issue Date2008
PublisherSpringer New York LLC. The Journal's web site is located at http://springerlink.metapress.com/openurl.asp?genre=journal&issn=1094-6136
Citation
Journal Of Scheduling, 2008, v. 11 n. 4, p. 299-308 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, J.-H., Chwa, K.-Y. in Theor. Comput. Sci. 325(3):479-488, 2004) which is shown to be 5-competitive by (Chan, W.-T., et al. in Lecture Notes in Computer Science, vol. 3106, pp. 210-218, 2004). In the case that pages may have different lengths, we give a (Δ + 2√Δ + 2)-competitive algorithm where Δ is the ratio of maximum to minimum page lengths. This improves the (4Δ+3)-competitive algorithm of (Chan, W.-T., et al. in Lecture Notes in Computer Science, vol. 3106, pp. 210-218, 2004). We also prove an almost matching lower bound of Ω(Δ/ log∈Δ). Furthermore, for small values of Δ we give better lower bounds. © 2007 Springer Science+Business Media, LLC.
Persistent Identifierhttp://hdl.handle.net/10722/152398
ISSN
2023 Impact Factor: 1.4
2023 SCImago Journal Rankings: 0.793
ISI Accession Number ID
References

 

DC FieldValueLanguage
dc.contributor.authorFung, SPYen_US
dc.contributor.authorZheng, Fen_US
dc.contributor.authorChan, WTen_US
dc.contributor.authorChin, FYLen_US
dc.contributor.authorPoon, CKen_US
dc.contributor.authorWong, PWHen_US
dc.date.accessioned2012-06-26T06:38:03Z-
dc.date.available2012-06-26T06:38:03Z-
dc.date.issued2008en_US
dc.identifier.citationJournal Of Scheduling, 2008, v. 11 n. 4, p. 299-308en_US
dc.identifier.issn1094-6136en_US
dc.identifier.urihttp://hdl.handle.net/10722/152398-
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, J.-H., Chwa, K.-Y. in Theor. Comput. Sci. 325(3):479-488, 2004) which is shown to be 5-competitive by (Chan, W.-T., et al. in Lecture Notes in Computer Science, vol. 3106, pp. 210-218, 2004). In the case that pages may have different lengths, we give a (Δ + 2√Δ + 2)-competitive algorithm where Δ is the ratio of maximum to minimum page lengths. This improves the (4Δ+3)-competitive algorithm of (Chan, W.-T., et al. in Lecture Notes in Computer Science, vol. 3106, pp. 210-218, 2004). We also prove an almost matching lower bound of Ω(Δ/ log∈Δ). Furthermore, for small values of Δ we give better lower bounds. © 2007 Springer Science+Business Media, LLC.en_US
dc.languageengen_US
dc.publisherSpringer New York LLC. The Journal's web site is located at http://springerlink.metapress.com/openurl.asp?genre=journal&issn=1094-6136en_US
dc.relation.ispartofJournal of Schedulingen_US
dc.subjectBroadcast Schedulingen_US
dc.subjectCompetitive Analysisen_US
dc.subjectOnline Algorithmsen_US
dc.titleImproved on-line broadcast scheduling with deadlinesen_US
dc.typeArticleen_US
dc.identifier.emailChin, FYL:chin@cs.hku.hken_US
dc.identifier.authorityChin, FYL=rp00105en_US
dc.description.naturelink_to_subscribed_fulltexten_US
dc.identifier.doi10.1007/s10951-007-0036-6en_US
dc.identifier.scopuseid_2-s2.0-49549100272en_US
dc.relation.referenceshttp://www.scopus.com/mlt/select.url?eid=2-s2.0-49549100272&selection=ref&src=s&origin=recordpageen_US
dc.identifier.volume11en_US
dc.identifier.issue4en_US
dc.identifier.spage299en_US
dc.identifier.epage308en_US
dc.identifier.isiWOS:000258454800006-
dc.publisher.placeUnited Statesen_US
dc.identifier.scopusauthoridFung, SPY=7201970079en_US
dc.identifier.scopusauthoridZheng, F=9276481100en_US
dc.identifier.scopusauthoridChan, WT=7403918060en_US
dc.identifier.scopusauthoridChin, FYL=7005101915en_US
dc.identifier.scopusauthoridPoon, CK=7202673523en_US
dc.identifier.scopusauthoridWong, PWH=9734871500en_US
dc.identifier.issnl1094-6136-

Export via OAI-PMH Interface in XML Formats


OR


Export to Other Non-XML Formats