## Abstract

In this paper we study the following problem. There are n pages which clients can request at any time. The arrival times of requests for pages are known. Several requests for the same page may arrive at different times. There is a server that needs to compute a good broadcast schedule. Outputting a page satisfies all outstanding requests for the page. The goal is to minimize the average waiting time of a client. This problem has recently been shown to be NP-hard. For any fixed α, 0 < α ≤ 1/2, we give a 1/α- speed, polynomial time algorithm with an approximation ratio of 1/1-α. For example, setting α = 1/2 gives a 2-speed, 2-approximation algorithm. In addition, we give a 4-speed, 1-approximation algorithm improving the previous bound of 6-speed, 1-approximation algorithm.

Original language | English (US) |
---|---|

Pages (from-to) | 425-438 |

Number of pages | 14 |

Journal | Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics) |

Volume | 2337 LNCS |

State | Published - Dec 1 2002 |

Event | 9th International Conference on Integer Programming and Combinatorial Optimization, IPCO 2002 - Cambridge, MA, United States Duration: May 27 2002 → May 29 2002 |

## ASJC Scopus subject areas

- Theoretical Computer Science
- General Computer Science