Approximating the average response time in broadcast scheduling
Bansal, N Nikhil, Charikar, M, Khanna, S, Naor, J · 2005
We consider the problem of approximating the minimum average response time in on-denmnd 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(x/n)-approximation, where n is the number of distinct pages. Our result can be extended, for any e> 0, to a (1 + e)-speed, additive O(1/e)-approximation algorithm. Prior to our work, no non-trivial approxinmtion factor was known for the case of e < 1. 1 I n t roduct ion We consider the problem of minimizing the average response t ime in on-demand ata broadcasting systems. In this setting, clients communicate with a powerful server through two independent networks: a network