| 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-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 (d_max <= u_min), a case for which an algorithm with ratio (3,1) was presented by
Skutella. |
