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.
展开▼
机译：我们考虑广播调度的版本，在该版本中，服务器可以在每个时间步长发送给定集合的一条消息，以响应先前对该消息的请求。目标是如果每个时间步长和消息的请求量事先已知，则将平均响应时间减至最小。我们证明此问题是NP难题，因此回答了Kalyanasundaram，Pruhs和Velauthapillai提出的一个开放性问题（《欧洲航天局2000年会议记录》，LNCS 1879年，2000年，第290-301页）。此外，我们提出了一种近似算法，该算法允许一次发送多个消息。使用6个通道进行传输，该算法获得的平均响应时间至少与使用一个通道的最佳解决方案一样好。最好的先前近似算法在6个信道上达到1.5的比率，并且仅在消息数量与信道相同的情况下才达到1比率。根据广播调度的NP硬度，我们得出了（2-ε，1）的新的不可近似性结果对于单源不可分割的最小成本流问题的（拥塞，成本）双标准版本，任意ε>0。即使在通常考虑的情况下，最大需求小于或等于最小边缘容量（ d max ≤ u min ），提出了比率为（3，1）的算法由Skutella。
展开▼
