Please use this identifier to cite or link to this item:
Title: NP-Hardness of Broadcast Scheduling and Inapproximability of Single-Source Unsplittable Min-Cost Flow
Authors: Erlebach, T.
Hall, A.
First Published: 2004
Citation: Journal of Scheduling, 2004, 7 (3), pp.223-241
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 (ART) 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 six channels for transmissions, the algorithm achieves an ART 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 − ε, 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 (d max ≤ u min), a case for which an algorithm with ratio (3, 1) was presented by Skutella.
DOI Link: 10.1023/B:JOSH.0000019682.75022.96
ISSN: 1094-6136
Type: Article
Appears in Collections:Published Articles, Dept. of Computer Science

Files in This Item:
There are no files associated with this item.

Items in LRA are protected by copyright, with all rights reserved, unless otherwise indicated.