论文部分内容阅读
Green data transmission is important for wireless networks,such as sensor networks, mobile networks, etc.This paper gives approximation algorithms for constructing energy constrained minimum cost Steiner trees (ECMST), a topology for data multicast considering both saving energy and minimizing the occupied resource.For a given undirected graph, in which each edge is with nonnegative integral cost and energy consumption, the ECMST problem is to compute a minimum cost tree spanning all specified terminals and satisfying a given energy consumption constraint.Apparently ECMST is NP-hard, since it includes the minimum Steiner tree problem which is known NP-hard.In the paper, we first presents an approximation algorithm by extending Byrka et al.s method [3] via Lagrangian relaxation.Then, we improve the ratio of the approximation algorithm to (9, 3) by replacing components of the computed Steiner tree.The improvement is mainly based on three ingredients: a generalization of the k-Steiner ratio against ECMST, the observation that ECMST is pseudo-polynomial solvable when the number of the terminals are fixed, and the extension of Byrka and et al.s approximation algorithm.To the best of our knowledge, our algorithm is with the best ratio in the current state of the art.Although Ravi and Goemans [21] have proposed a (1 + ε, 1)-approximation algorithm for the special case when all vertices are terminals, their method can not be applied to ECMST, since their method is based on a matroid property which doesnt ho]d for ECMST.