File Download

There are no files associated with this item.

  Links for fulltext
     (May Require Subscription)
Supplementary

Conference Paper: Off-line algorithms for minimizing total flow time in broadcast scheduling

TitleOff-line algorithms for minimizing total flow time in broadcast scheduling
Authors
Issue Date2005
PublisherSpringer Verlag. The Journal's web site is located at http://springerlink.com/content/105633/
Citation
Lecture Notes In Computer Science, 2005, v. 3595, p. 318-328 How to Cite?
AbstractWe study the off-line broadcast scheduling problem to minimize total (or average) flow time. Assume the server has k pages and the requests arrive at n distinct times, we give the first algorithm to find the optimal schedule for the server with a single channel, in O(k3(n + k)k-1) time. For m-channel case, i.e., the server can broadcast m different pages at a time where m < k, we find the optimal schedule in O(nk-m) time when k and m are constants. In the single channel case, we also give a simple linear-time approximation algorithm to minimize average flow time, which achieves an additive (k - 1)/2-approximation. © Springer-Verlag Berlin Heidelberg 2005.
Persistent Identifierhttp://hdl.handle.net/10722/93020
ISSN
2005 Impact Factor: 0.402
2015 SCImago Journal Rankings: 0.252
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.accessioned2010-09-25T14:48:27Z-
dc.date.available2010-09-25T14:48:27Z-
dc.date.issued2005en_HK
dc.identifier.citationLecture Notes In Computer Science, 2005, v. 3595, p. 318-328en_HK
dc.identifier.issn0302-9743en_HK
dc.identifier.urihttp://hdl.handle.net/10722/93020-
dc.description.abstractWe study the off-line broadcast scheduling problem to minimize total (or average) flow time. Assume the server has k pages and the requests arrive at n distinct times, we give the first algorithm to find the optimal schedule for the server with a single channel, in O(k3(n + k)k-1) time. For m-channel case, i.e., the server can broadcast m different pages at a time where m < k, we find the optimal schedule in O(nk-m) time when k and m are constants. In the single channel case, we also give a simple linear-time approximation algorithm to minimize average flow time, which achieves an additive (k - 1)/2-approximation. © Springer-Verlag Berlin Heidelberg 2005.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.titleOff-line algorithms for minimizing total flow time in broadcast schedulingen_HK
dc.typeConference_Paperen_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-26844506287en_HK
dc.identifier.hkuros102735en_HK
dc.relation.referenceshttp://www.scopus.com/mlt/select.url?eid=2-s2.0-26844506287&selection=ref&src=s&origin=recordpageen_HK
dc.identifier.volume3595en_HK
dc.identifier.spage318en_HK
dc.identifier.epage328en_HK
dc.publisher.placeGermanyen_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