## 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(k^{3}(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(n^{k-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 language | English |
---|---|

Pages (from-to) | 318-328 |

Number of pages | 11 |

Journal | Lecture Notes in Computer Science |

Volume | 3595 |

DOIs | |

Publication status | Published - 2005 |

Externally published | Yes |

Event | 11th Annual International Conference on Computing and Combinatorics, COCOON 2005 - Kunming, China Duration: 16 Aug 2005 → 29 Aug 2005 |