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² (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].

REFERENCES

• 1: A. Ageev and M. Sviridenko, Pipage Rounding: a New Method of Constructing Algorithms with Proven Performance Guarantee. Journal of Combinatorial Optimization, 8, 2004.
• 2: Airmedia website, http://www.airmedia.com.
• 3: Nikhil Bansal , Moses Charikar , Sanjeev Khanna , Joseph (Seffi) Naor, Approximating the average response time in broadcast scheduling, Proceedings of the sixteenth annual ACM-SIAM symposium on Discrete algorithms, January 23-25, 2005, Vancouver, British Columbia
• 4: Amotz Bar-Noy , Sudipto Guha , Yoav Katz , Joseph (Seffi) Naor , Baruch Schieber , Hadas Shachnai, Throughput maximization of real-time scheduling with batching, Proceedings of the thirteenth annual ACM-SIAM symposium on Discrete algorithms, p.742-751, January 06-08, 2002, San Francisco, California
• 5: 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
• 6: Bernard Chazelle, The discrepancy method: randomness and complexity, Cambridge University Press, New York, NY, 2000
• 7: DirecPC website, http://www.direcpc.com.
• 8: 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
• 9: 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
• 10: 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
• 11: R. Gailis and S. Khuller. Broadcast Scheduling with Deadlines. Unpublished Manuscript.
• 12: R. Gandhi, S. Khuller, Y. Kim and Y-C. Wan. Approximation algorithms for broadcast scheduling. Proc. of the 9th Conference on Integer Programming and Combinatorial Optimization (IPCO), 2002.
• 13: 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
• 14: Intel Intercast website, http://www.intercast.com.
• 15: 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
• 16: S. Khuller and Y. Kim, Equivalence of Two Linear Programming Relaxations for Broadcast Scheduling, Operations Research Letters, 32(5), 473--478, 2004.
• 17: K. Pruhs, J. Sgall, E. Torng, Online Scheduling. Handbook of Scheduling: Algorithms, Models, and Performance Analysis, editor Joseph Y-T. Leung, CRC Press, 2004.

INDEX TERMS

Primary Classification:
  G. Mathematics of Computing
  G.1 NUMERICAL ANALYSIS
      G.1.2 Approximation

Additional Classification:
  F. Theory of Computation
  F.2 ANALYSIS OF ALGORITHMS AND PROBLEM COMPLEXITY
      F.2.2 Nonnumerical Algorithms and Problems
          Subjects: Sequencing and scheduling

  I. Computing Methodologies
  I.2 ARTIFICIAL INTELLIGENCE
      I.2.8 Problem Solving, Control Methods, and Search
          Subjects: Scheduling

General Terms:
Algorithms, Theory