File Download
  Links for fulltext
     (May Require Subscription)
Supplementary

Article: A dynamic programming approach of finding an optimal broadcast schedule in minimizing total flow time

TitleA dynamic programming approach of finding an optimal broadcast schedule in minimizing total flow time
Authors
KeywordsBroadcast scheduling
Dynamic programming
Flow time minimization
Issue Date2006
PublisherSpringer Verlag Dordrecht. The Journal's web site is located at http://springerlink.metapress.com/openurl.asp?genre=journal&issn=1382-6905
Citation
Journal Of Combinatorial Optimization, 2006, v. 11 n. 2, p. 177-187 How to Cite?
AbstractWe study the problem of (off-line) broadcast scheduling in minimizing total flow time and propose a dynamic programming approach to compute an optimal broadcast schedule. Suppose the broadcast server has k pages and the last page request arrives at time n. The optimal schedule can be computed in O(k 3(n + k)k-1) time for the case that the server has a single broadcast channel. For m channels case, i.e., the server can broadcast m different pages at a time where m < k, the optimal schedule can be computed in O(nk-m) time when k and m are constants. Note that this broadcast scheduling problem is NP-hard when k is a variable and will take O(n k-m+1) time when k is fixed and m ≥ 1 with the straightforward implementation of the dynamic programming approach. © Springer Science + Business Media, LLC 2006.
DescriptionProceedings of the 11th Annual International Computing and Combinatorics Conference as 'Off-line Algorithms for Minimizing the Total Flow Time in Broadcast Scheduling'
Persistent Identifierhttp://hdl.handle.net/10722/53595
ISSN
2015 Impact Factor: 1.08
2015 SCImago Journal Rankings: 1.093
ISI Accession Number ID
References

 

DC FieldValueLanguage
dc.contributor.authorChan, WTen_HK
dc.contributor.authorChin, FYLen_HK
dc.contributor.authorZhang, Yen_HK
dc.contributor.authorZhu, Hen_HK
dc.contributor.authorShen, Hen_HK
dc.contributor.authorWong, PWHen_HK
dc.date.accessioned2009-04-03T07:24:10Z-
dc.date.available2009-04-03T07:24:10Z-
dc.date.issued2006en_HK
dc.identifier.citationJournal Of Combinatorial Optimization, 2006, v. 11 n. 2, p. 177-187en_HK
dc.identifier.issn1382-6905en_HK
dc.identifier.urihttp://hdl.handle.net/10722/53595-
dc.descriptionProceedings of the 11th Annual International Computing and Combinatorics Conference as 'Off-line Algorithms for Minimizing the Total Flow Time in Broadcast Scheduling'en_HK
dc.description.abstractWe study the problem of (off-line) broadcast scheduling in minimizing total flow time and propose a dynamic programming approach to compute an optimal broadcast schedule. Suppose the broadcast server has k pages and the last page request arrives at time n. The optimal schedule can be computed in O(k 3(n + k)k-1) time for the case that the server has a single broadcast channel. For m channels case, i.e., the server can broadcast m different pages at a time where m < k, the optimal schedule can be computed in O(nk-m) time when k and m are constants. Note that this broadcast scheduling problem is NP-hard when k is a variable and will take O(n k-m+1) time when k is fixed and m ≥ 1 with the straightforward implementation of the dynamic programming approach. © Springer Science + Business Media, LLC 2006.en_HK
dc.languageengen_HK
dc.publisherSpringer Verlag Dordrecht. The Journal's web site is located at http://springerlink.metapress.com/openurl.asp?genre=journal&issn=1382-6905en_HK
dc.relation.ispartofJournal of Combinatorial Optimizationen_HK
dc.rightsCreative Commons: Attribution 3.0 Hong Kong License-
dc.subjectBroadcast schedulingen_HK
dc.subjectDynamic programmingen_HK
dc.subjectFlow time minimizationen_HK
dc.titleA dynamic programming approach of finding an optimal broadcast schedule in minimizing total flow timeen_HK
dc.typeArticleen_HK
dc.identifier.openurlhttp://library.hku.hk:4550/resserv?sid=HKU:IR&issn=1382-6905&volume=11&issue=2&spage=177&epage=187&date=2006&atitle=A+Dynamic+Programming+Approach+Of+Finding+An+Optimal+Broadcast+Schedule+In+Minimizing+Total+Flow+Timeen_HK
dc.identifier.emailChin, FYL:chin@cs.hku.hken_HK
dc.identifier.authorityChin, FYL=rp00105en_HK
dc.description.naturepostprinten_HK
dc.identifier.doi10.1007/s10878-006-7128-7en_HK
dc.identifier.scopuseid_2-s2.0-33646534849en_HK
dc.relation.referenceshttp://www.scopus.com/mlt/select.url?eid=2-s2.0-33646534849&selection=ref&src=s&origin=recordpageen_HK
dc.identifier.volume11en_HK
dc.identifier.issue2en_HK
dc.identifier.spage177en_HK
dc.identifier.epage187en_HK
dc.identifier.isiWOS:000236792900005-
dc.publisher.placeNetherlandsen_HK
dc.identifier.scopusauthoridChan, WT=7403918060en_HK
dc.identifier.scopusauthoridChin, FYL=7005101915en_HK
dc.identifier.scopusauthoridZhang, Y=7601329213en_HK
dc.identifier.scopusauthoridZhu, H=7404663553en_HK
dc.identifier.scopusauthoridShen, H=7404522601en_HK
dc.identifier.scopusauthoridWong, PWH=9734871500en_HK

Export via OAI-PMH Interface in XML Formats


OR


Export to Other Non-XML Formats