Approximating the average response time in broadcast scheduling

We consider the problem of approximating the minimum average response time in on-demand data broadcasting systems. The best approximation factors known for this problem involve resource augmentation. We provide the first non-trivial approximation factors in the absence of resource augmentation, achieving an additive O(√n)-approximation, where n is the number of distinct pages. Our result can be extended, for any ε > 0, to a (1 + ε)-speed, additive O(1/ε)-approximation algorithm. Prior to our work, no non-trivial approximation factor was known for the case of ε < 1.