Indexed by:
Abstract:
Nowadays, two issues in data transmission for networks are attracting considerable interest in the research community: energy efficiency and cost minimization, i. e., to minimize the energy consumed and resource occupied. This paper considers approximation algorithms for the energy constrained minimum cost Steiner tree (ECMST) problem which have applications in energy-efficient minimum cost multicast. Let G = (V, E) be a given undirected graph, S ⊆ V be a terminal set, and c: E → Z+0 and d: E → Z+0 respectively be the cost function and energy consumption function for the edges. For a threshold D, ECMST is to compute a minimum cost tree spanning all specified terminals of S, with its total energy consumption bounded by D. This paper first shows that ECMST is pseudo-polynomial solvable when the number of the terminals are fixed. Then it presents a polynomial time factor- (2(1+ 1/k), 2(1+k)) approximation algorithm via Lagrangian Relaxation for any k > 0. Last but not the least, by a more sophisticated application of Lagrangian relaxation technique, we obtain an approximation algorithm with ratio (2, 2 + Ε) for any fixed Ε > 0. © Springer International Publishing Switzerland 2015.
Keyword:
Reprint 's Address:
Email:
Version:
Source :
ISSN: 0302-9743
Year: 2015
Volume: 9528
Page: 567-577
Language: English
0 . 4 0 2
JCR@2005
Cited Count:
SCOPUS Cited Count: 1
ESI Highly Cited Papers on the List: 0 Unfold All
WanFang Cited Count:
Chinese Cited Count:
30 Days PV: 0
Affiliated Colleges: