File Download
There are no files associated with this item.
Supplementary
-
Citations:
- Scopus: 0
- Appears in Collections:
Conference Paper: Off-line algorithms for minimizing total flow time in broadcast scheduling
Title | Off-line algorithms for minimizing total flow time in broadcast scheduling |
---|---|
Authors | |
Issue Date | 2005 |
Publisher | Springer 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? |
Abstract | We 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 Identifier | http://hdl.handle.net/10722/93020 |
ISSN | 2023 SCImago Journal Rankings: 0.606 |
References |
DC Field | Value | Language |
---|---|---|
dc.contributor.author | Chan, WT | en_HK |
dc.contributor.author | Chin, FYL | en_HK |
dc.contributor.author | Zhang, Y | en_HK |
dc.contributor.author | Zhu, H | en_HK |
dc.contributor.author | Shen, H | en_HK |
dc.contributor.author | Wong, PWH | en_HK |
dc.date.accessioned | 2010-09-25T14:48:27Z | - |
dc.date.available | 2010-09-25T14:48:27Z | - |
dc.date.issued | 2005 | en_HK |
dc.identifier.citation | Lecture Notes In Computer Science, 2005, v. 3595, p. 318-328 | en_HK |
dc.identifier.issn | 0302-9743 | en_HK |
dc.identifier.uri | http://hdl.handle.net/10722/93020 | - |
dc.description.abstract | We 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.language | eng | en_HK |
dc.publisher | Springer Verlag. The Journal's web site is located at http://springerlink.com/content/105633/ | en_HK |
dc.relation.ispartof | Lecture Notes in Computer Science | en_HK |
dc.title | Off-line algorithms for minimizing total flow time in broadcast scheduling | en_HK |
dc.type | Conference_Paper | en_HK |
dc.identifier.email | Chin, FYL:chin@cs.hku.hk | en_HK |
dc.identifier.authority | Chin, FYL=rp00105 | en_HK |
dc.description.nature | link_to_subscribed_fulltext | - |
dc.identifier.scopus | eid_2-s2.0-26844506287 | en_HK |
dc.identifier.hkuros | 102735 | en_HK |
dc.relation.references | http://www.scopus.com/mlt/select.url?eid=2-s2.0-26844506287&selection=ref&src=s&origin=recordpage | en_HK |
dc.identifier.volume | 3595 | en_HK |
dc.identifier.spage | 318 | en_HK |
dc.identifier.epage | 328 | en_HK |
dc.publisher.place | Germany | en_HK |
dc.identifier.scopusauthorid | Chan, WT=7403918060 | en_HK |
dc.identifier.scopusauthorid | Chin, FYL=7005101915 | en_HK |
dc.identifier.scopusauthorid | Zhang, Y=7601329213 | en_HK |
dc.identifier.scopusauthorid | Zhu, H=7404663553 | en_HK |
dc.identifier.scopusauthorid | Shen, H=7404522601 | en_HK |
dc.identifier.scopusauthorid | Wong, PWH=9734871500 | en_HK |
dc.identifier.issnl | 0302-9743 | - |