| Abstract: |
We consider the version of broadcast scheduling where a server can transmit W messages of a given set at each time-step, answering previously made requests for these messages. 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. From the NP-hardness of
broadcast scheduling we derive a new inapproximability result of (2-eps,1) for the (congestion,cost) bicriteria version of the single source unsplittable min-cost flow problem, for arbitrary
eps>0. The result holds even in the often considered case where the maximum demand is less than or equal to the minimum edge capacity (dmaxle umin), a case
for which an algorithm with ratio (3,1) was presented by Skutella. |
