Broadcast scheduling: algorithms and complexity

ABSTRACT

Broadcast Scheduling is a popular method for disseminating information in response to client requests. There are n pages of information, and clients request pages at different times. However, multiple clients can have their requests satisfied by a single broadcast of the requested page. In this paper we consider several related broadcast scheduling problems. One central problem we study simply asks to minimize the maximum response time (over all requests). Another related problem we consider is the version in which every request has a release time and a deadline, and the goal is to maximize the number of requests that meet their deadlines. While approximation algorithms for both these problems were proposed several years back, it was not known if they were NP-complete. One of our main results is that both these problems are NP-complete. In addition, we use the same unified approach to give a simple NP-completeness proof for minimizing the sum of response times. A very complicated proof was known for this version. Furthermore, we give a proof that FIFO is a 2-competitive online algorithm for minimizing the maximum response time (this result had been claimed earlier with no proof) and that there is no better deterministic online algorithm (this result was claimed earlier as well, but with an incorrect proof).

REFERENCES

• 1: S. Acharya, M. Franklin, and S. Zdonik. Dissemination-based data delivery using broadcast disks. In IEEE Personal Communications, 2(6):50--60, 1995.
• 2: Demet Aksoy , Michael Franklin, R × W: a scheduling approach for large-scale on-demand data broadcast, IEEE/ACM Transactions on Networking (TON), v.7 n.6, p.846-860, Dec. 1999 [doi>10.1109/90.811450]
• 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: Nikhil Bansal , Don Coppersmith , Maxim Sviridenko, Improved approximation algorithms for broadcast scheduling, Proceedings of the seventeenth annual ACM-SIAM symposium on Discrete algorithm, p.344-353, January 22-26, 2006, Miami, Florida [doi>10.1145/1109557.1109596]
• 5: Amotz Bar-Noy , Randeep Bhatia , Joseph (Seffi) Naor , Baruch Schieber, Minimizing service and operation costs of periodic scheduling, Proceedings of the ninth annual ACM-SIAM symposium on Discrete algorithms, p.11-20, January 25-27, 1998, San Francisco, California, United States
• 6: 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
• 7: 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
• 8: W. Chan, T. Lam, H. Ting, and P. Wong. New results on on-demand broadcasting with deadline via job scheduling with cancellation. In 10th COCOON, LNCS 3106, Springer-Verlag, 210--218, 2004.
• 9: Moses Charikar , Samir Khuller, A robust maximum completion time measure for scheduling, Proceedings of the seventeenth annual ACM-SIAM symposium on Discrete algorithm, p.324-333, January 22-26, 2006, Miami, Florida [doi>10.1145/1109557.1109594]
• 10: Marek Chrobak , Christoph Dürr , Wojciech Jawor , Łukasz Kowalik , Maciej Kurowski, A Note on Scheduling Equal-Length Jobs to Maximize Throughput, Journal of Scheduling, v.9 n.1, p.71-73, February 2006 [doi>10.1007/s10951-006-5595-4]
• 11: 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
• 12: 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
• 13: 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
• 14: 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
• 15: 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
• 16: Rajiv Gandhi , Samir Khuller , Srinivasan Parthasarathy , Aravind Srinivasan, Dependent rounding and its applications to approximation algorithms, Journal of the ACM (JACM), v.53 n.3, p.324-360, May 2006 [doi>10.1145/1147954.1147956]
• 17: 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
• 18: S. Khuller and Y. Kim. Equivalence of two linear programming relaxations for broadcast scheduling, Operations Research Letters Vol 32 (5): 473--478 (2004).
• 19: Jae-Hoon Kim , Kyung-Yong Chwa, Scheduling broadcasts with deadlines, Theoretical Computer Science, v.325 n.3, p.479-488, 6 October 2004 [doi>10.1016/j.tcs.2004.02.047]
• 20: J. Wong. Broadcast Delivery. In Proc. of the IEEE, 76(12):1566--1577, 1988.
• 21: F. Zheng, S. Fung, W. Chan, F. Chin, C. Poon and P. Wong. Improved online broadcast scheduling with deadlines. Proc. of the 11th International Computing and Combinatorics Conference (COCOON), pp. 320--329, (2006).

INDEX TERMS

Primary Classification:
  D. Software
  D.4 OPERATING SYSTEMS
      D.4.1 Process Management
          Subjects: Scheduling

Additional Classification:
  C. Computer Systems Organization
  C.2 COMPUTER-COMMUNICATION NETWORKS
      C.2.4 Distributed Systems
          Subjects: Client/server

  D. Software
  D.4 OPERATING SYSTEMS
      D.4.7 Organization and Design
          Subjects: Distributed systems

  F. Theory of Computation
  F.1 COMPUTATION BY ABSTRACT DEVICES
      F.1.2 Modes of Computation
          Subjects: Online computation
  F.2 ANALYSIS OF ALGORITHMS AND PROBLEM COMPLEXITY
      F.2.2 Nonnumerical Algorithms and Problems
          Subjects: Sequencing and scheduling

General Terms:
Algorithms, Design, Performance