Please use this identifier to cite or link to this item:
https://hdl.handle.net/2440/36939
Citations | ||
Scopus | Web of Science® | Altmetric |
---|---|---|
?
|
?
|
Type: | Conference paper |
Title: | Off-Line algorithms for minimizing total flow time in broadcast scheduling |
Author: | Chan, W. Chin, F. Zhang, Y. Zhu, H. Shen, H. Wong, P. |
Citation: | Computing and combinatorics : 11th annual international conference, COCOON 2005, Kunming, China, August 16-29, 2005 : proceedings / Lusheng Wang (ed.), pp. 318-328 |
Publisher: | Springer |
Publisher Place: | Berlin |
Issue Date: | 2005 |
ISBN: | 3540280618 9783540280613 |
ISSN: | 0302-9743 1611-3349 |
Conference Name: | COCOON 2005 (2005 : Kunming Shi, China) |
Statement of Responsibility: | Wun-Tat Chan, Francis Y.L. Chin, Yong Zhang, Hong Zhu, Hong Shen and Prudence W.H. Wong |
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. |
Description: | The original publication is available at www.springerlink.com |
DOI: | 10.1007/11533719_33 |
Published version: | http://www.springerlink.com/content/3mm1fk63f9ytnn7r/ |
Appears in Collections: | Aurora harvest 6 Computer Science publications |
Files in This Item:
There are no files associated with this item.
Items in DSpace are protected by copyright, with all rights reserved, unless otherwise indicated.