Algorithms for minimizing response time in broadcast scheduling

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 in advance. 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 < α ⩽ 0.5, we give a 1/α-speed, polynomial time algorithm with an approximation ratio of 1/(1 − α). For example, setting α=0.5; 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.