| |
| Green data transmission is important for wireless networks, such assensor networks, mobile networks, etc. This paper gives approximationalgorithms for constructing energy constrained minimum cost Steinertrees (ECMST), a topology for data multicast considering both savingenergy and minimizing the occupied resource. For a given undirectedgraph, in which each edge is with nonnegative integral cost and energyconsumption, the ECMST problem is to compute a minimum cost tree spanningall specified terminals and satisfying a given energy consumptionconstraint. Apparently ECMST is NP-hard, since it includes the minimumSteiner tree problem which is known NP-hard.The paper first presents an approximation algorithm by extendingByrka et al.'s method via Lagrangian relaxation. Then, the paper improves the ratio of the approximation algorithm to $(2,,3)$by replacing components of the computed Steiner tree. The improvementis mainly based on three ingredients: a generalization of the $k$-Steinerratio against ECMST, the observation that ECMST is pseudo-polynomialsolvable when the number of the terminals are fixed, and the extensionof Byrka and et al.'s approximation algorithm. To the best of ourknowledge, our algorithm is with the best ratio in the current stateof the art. Although Ravi and Goemanshave proposed a $(1+epsilon,,1)$-approximation algorithm for thespecial case when all vertices are terminals, their method can notbe applied to ECMST, since their method is based on a matroid propertywhich doesn't hold for ECMST. |
|
| Keywords:Algorithm design and analysis, Approximation algorithm, energy constrained minimum cost Steiner tree,Lagrangian relaxation, full component. |
|
