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

Wun Tat Chan, Francis Y.L. Chin, Yong Zhang, Hong Zhu, Hong Shen, Prudence W.H. Wong

Research output: Contribution to journalConference articlepeer-review

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.

Original languageEnglish
Pages (from-to)318-328
Number of pages11
JournalLecture Notes in Computer Science
Volume3595
DOIs
Publication statusPublished - 2005
Externally publishedYes
Event11th Annual International Conference on Computing and Combinatorics, COCOON 2005 - Kunming, China
Duration: 16 Aug 200529 Aug 2005

Fingerprint

Dive into the research topics of 'Off-line algorithms for minimizing total flow time in broadcast scheduling'. Together they form a unique fingerprint.

Cite this