Approximating Algorithms for Computing Energy Constrained Minimum Cost Steiner Trees
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 doesn”t ho”d for ECMST.
Approximation algorithm energy constrained minimum cost Steiner tree Lagrangian relaxation full component
Nianchen Zou Longkun Guo
College of Mathematics and Computer Science,Fuzhou University,China
国内会议
金华
英文
1-13
2015-10-30（万方平台首次上网日期，不代表论文的发表时间）