Approximating the average response time in broadcast scheduling

ABSTRACT

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.

REFERENCES

• 1: N. Alon, and J. Spencer, The Probabilistic Method. John Wiley & Sons, 2000.
• 2: Yair Bartal , S. Muthukrishnan, Minimizing maximum response time in scheduling broadcasts, Proceedings of the eleventh annual ACM-SIAM symposium on Discrete algorithms, p.558-559, January 09-11, 2000, San Francisco, California, United States
• 3: M. Bellare and J. Rompel. Randomness-Efficient Oblivious Sampling. Proc. of the 35th Annual IEEE Symposium on Foundations of Computer Science, pp. 276--287, 1994.
• 4: Jeff Edmonds , Kirk Pruhs, Broadcast scheduling: when fairness is fine, Proceedings of the thirteenth annual ACM-SIAM symposium on Discrete algorithms, p.421-430, January 06-08, 2002, San Francisco, California
• 5: Jeff Edmonds , Kirk Pruhs, A maiden analysis of Longest Wait First, Proceedings of the fifteenth annual ACM-SIAM symposium on Discrete algorithms, January 11-14, 2004, New Orleans, Louisiana
• 6: Thomas Erlebach , Alexander Hall, NP-hardness of broadcast scheduling and inapproximability of single-source unsplittable min-cost flow, Proceedings of the thirteenth annual ACM-SIAM symposium on Discrete algorithms, p.194-202, January 06-08, 2002, San Francisco, California
• 7: Rajiv Gandhi , Samir Khuller , Yoo Ah Kim , Yung-Chun Wan, Algorithms for Minimizing Response Time in Broadcast Scheduling, Proceedings of the 9th International IPCO Conference on Integer Programming and Combinatorial Optimization, p.425-438, May 27-29, 2002
• 8: Rajiv Gandhi , Samir Khuller , Srinivasan Parthasarathy , Aravind Srinivasan, Dependent Rounding in Bipartite Graphs, Proceedings of the 43rd Symposium on Foundations of Computer Science, p.323-332, November 16-19, 2002
• 9: Bala Kalyanasundaram , Kirk Pruhs , Mahendran Velauthapillai, Scheduling Broadcasts in Wireless Networks, Proceedings of the 8th Annual European Symposium on Algorithms, p.290-301, September 05-08, 2000
• 10: K. Pruhs, J. Sgall, E. Torng, Online Scheduling. Handbook of Scheduling: Algorithms, Models, and Performance Analysis, editor Joseph Y-T. Leung, CRC Press, 2004.