NP-hardness of broadcast scheduling and inapproximability of single-source unsplittable min-cost flow

NP-hardness of broadcast scheduling and inapproximability of single-source unsplittable min-cost flow

0.00 Avg rating0 Votes
Article ID: iaor2008181
Country: United Kingdom
Volume: 7
Issue: 3
Start Page Number: 223
End Page Number: 241
Publication Date: May 2004
Journal: Journal of Scheduling
Authors: ,
Keywords: communications, networks: flow
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 et al. 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 (dmaxumin), a case for which an algorithm with ratio (3, 1) was presented by Skutella.

Reviews

Required fields are marked *. Your email address will not be published.