Please use this identifier to cite or link to this item:
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
ISSN: 0302-9743
Conference Name: COCOON 2005 (2005 : Kunming Shi, China)
Statement of
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
DOI: 10.1007/11533719_33
Published version:
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.