Improved approximation algorithms for broadcast scheduling

Abstract

We consider two scheduling problems in the broadcast setting. The first is that of minimizing the average response time of requests. For the offline version of this problem we give an algorithm with an approximation ratio of O(log 2(n)/ log log(n)), where n is the total number of pages. This substantially improves the previously best known approximation factor of O(√n) for the problem [3]. Our second result is for the profit maximization version of the broadcast scheduling problem. Here each request has a deadline and a profit which is obtained if the request is satisfied before its deadline. The goal is to maximize the total profit. We give an algorithm with an approximation ratio of 5/6, which improves the previously best known approximation guarantee of 3/4 for the problem [13].