NP-hardness of broadcast scheduling and inapproximability of single-source unsplittable min-cost flow

ABSTRACT

We consider the version of broadcast scheduling where a server can transmit one message of a given set at each time-step, answering previously made requests for that message. The goal is to minimize the average response time if the amount of requests is known in advance for each time-step and message. We prove that this problem is NP-hard, thus answering an open question stated by Kalyanasundaram, Pruhs and Velauthapillai (Proceedings of ESA 2000, LNCS 1879, 2000, pp. 290-301). Furthermore, we present an approximation algorithm that is allowed to send several messages at once. Using 6 channels for transmissions, the algorithm achieves an average response time that is at least as good as the optimal solution using one channel. The best previous approximation algorithm achieved ratio 1.5 with 6 channels and reached ratio 1 only in the case where there are as many channels as messages.From the NP-hardness of broadcast scheduling we derive a new inapproximability result of (2-ε, 1) for the (congestion,cost) bicriteria version of the single source unsplittable min-cost flow problem, for arbitrary ε > 0. The result holds even in the often considered case where the maximum demand is less than or equal to the minimum edge capacity (dmax ≤ umin), a case for which an algorithm with ratio (3, 1) was presented by Skutella.

REFERENCES

• 1: Swarup Acharya , S. Muthukrishnan, Scheduling on-demand broadcasts: new metrics and algorithms, Proceedings of the 4th annual ACM/IEEE international conference on Mobile computing and networking, p.43-54, October 25-30, 1998, Dallas, Texas, United States [doi>10.1145/288235.288248]
• 2: Amotz Bar-Noy , Randeep Bhatia , Joseph 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
• 3: 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
• 4: Y. Dinitz, N. Garg, M. Goemans. On the single source unsplittable flow problem, Combinatorica, 19 (1999), pp. 1-25.
• 5: 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
• 6: Bala Kalyanasundaram , Kirk Pruhs, Speed is as powerful as clairvoyance, Journal of the ACM (JACM), v.47 n.4, p.617-643, July 2000 [doi>10.1145/347476.347479]
• 7: 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
• 8: Claire Kenyon , Nicolas Schabanel, The data broadcast problem with non-uniform transmission times, Proceedings of the tenth annual ACM-SIAM symposium on Discrete algorithms, p.547-556, January 17-19, 1999, Baltimore, Maryland, United States
• 9: Claire Kenyon , Nicolas Schabanel , Neal Young, Polynomial-time approximation scheme for data broadcast, Proceedings of the thirty-second annual ACM symposium on Theory of computing, p.659-666, May 21-23, 2000, Portland, Oregon, United States [doi>10.1145/335305.335398]
• 10: Cynthia A. Phillips , Cliff Stein , Eric Torng , Joel Wein, Optimal time-critical scheduling via resource augmentation (extended abstract), Proceedings of the twenty-ninth annual ACM symposium on Theory of computing, p.140-149, May 04-06, 1997, El Paso, Texas, United States [doi>10.1145/258533.258570]
• 11: Nicolas Schabanel, The Data Broadcast Problem with Preemption, Proceedings of the 17th Annual Symposium on Theoretical Aspects of Computer Science, p.181-192, February 01, 2000
• 12: M. Skutella, Approximating the single source unsplittable min-cost flow problem, Proceedings of the 41st Annual Symposium on Foundations of Computer Science, p.136, November 12-14, 2000