NP-hardness of broadcast scheduling and inapproximability of single-source unsplittable min-cost flow
Open access
Date
2001-08Type
- Report
ETH Bibliography
yes
Altmetrics
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. Show more
Permanent link
https://doi.org/10.3929/ethz-a-004256732Publication status
publishedJournal / series
TIK ReportVolume
Publisher
ETH Zurich, Computer Engineering and Networks LaboratoryEdition / version
Version 1Organisational unit
02640 - Inst. f. Technische Informatik und Komm. / Computer Eng. and Networks Lab.
Related publications and datasets
Is previous version of: http://hdl.handle.net/20.500.11850/50601
More
Show all metadata
ETH Bibliography
yes
Altmetrics