Title: 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-e, 1) for the (congestion,cost) bicriteria version of the single source unsplittable min-cost flow problem, for arbitrary e > 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.
Publication Year: 2002
Publication Date: 2002-01-06
Language: en
Type: article
Access and Citation
Cited By Count: 51
AI Researcher Chatbot
Get quick answers to your questions about the article from our AI researcher chatbot