Advertisement
Published in:
2015 | OriginalPaper | Chapter
The Directed Ring Loading with Penalty Cost
Authors : Li Guan, Jianping Li, Xuejie Zhang, Weidong Li
Published in: WALCOM: Algorithms and Computation
Publisher: Springer International Publishing
Activate our intelligent search to find suitable subject content or patents.
Select sections of text to find matching patents with Artificial Intelligence. powered by
Select sections of text to find additional relevant content using AI-assisted search. powered by
We study the directed ring loading problem with penalty cost, which is to select some of given multicast requests represented by hyperedges with different demands and embed them in a directed ring, such that the sum of the maximum congestion among all links on the ring and the total penalty cost of the unselected multicast requests is minimized. We prove that this problem is
NP
-hard even if the demand is divisible, and then design a 1.582-approximation algorithm for the demand divisible case and a 3-approximation algorithm for the demand indivisible case, respectively. As a consequence, for any
ε
> 0, we present a (1.582 +
ε
)-approximation algorithm for the case where every multicast request contains exactly one sink.