• Complex
  • Title
  • Keyword
  • Abstract
  • Scholars
  • Journal
  • ISSN
  • Conference
成果搜索

author:

Zou, Nianchen (Zou, Nianchen.) [1] | Guo, Longkun (Guo, Longkun.) [2] (Scholars:郭龙坤)

Indexed by:

EI Scopus

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:

Approximation algorithms Cost functions Energy efficiency Energy utilization Lagrange multipliers Network architecture Parallel architectures Polynomial approximation Trees (mathematics)

Community:

  • [ 1 ] [Zou, Nianchen]College of Mathematics and Computer Science, Fuzhou University, Fuzhou; 350108, China
  • [ 2 ] [Guo, Longkun]College of Mathematics and Computer Science, Fuzhou University, Fuzhou; 350108, China

Reprint 's Address:

  • 郭龙坤

    [guo, longkun]college of mathematics and computer science, fuzhou university, fuzhou; 350108, china

Show more details

Version:

Related Keywords:

Related Article:

Source :

ISSN: 0302-9743

Year: 2015

Volume: 9528

Page: 567-577

Language: English

0 . 4 0 2

JCR@2005

Cited Count:

WoS CC 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

Online/Total:116/10047060
Address:FZU Library(No.2 Xuyuan Road, Fuzhou, Fujian, PRC Post Code:350116) Contact Us:0591-22865326
Copyright:FZU Library Technical Support:Beijing Aegean Software Co., Ltd. 闽ICP备05005463号-1