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(vn)-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 approximation factor was known for the case of e <1.
|Title of host publication||Proceedings of the Sixteenth Annual ACM-SIAM Symposium on Discrete Algorithms (SODA'05, Vancouver BC, Canada, January 23-25, 2005)|
|Place of Publication||New York|
|Publisher||Association for Computing Machinery, Inc|
|Publication status||Published - 2005|