NP-hardness of broadcast scheduling and inapproximability of single-source unsplittable min-cost flow
Thomas Erlebach, Alexander Hall · 2002
We consider the version of broadcast scheduling where a server can transmit one message of a given set at each timestep, 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