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 < α \le 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.
- Approximation algorithms
ASJC Scopus subject areas
- Computer Science(all)
- Computer Science Applications
- Applied Mathematics