APPROXIMATE MIN-POWER STRONG CONNECTIVITY

作者：Calinescu G^*

来源：SIAM Journal on Discrete Mathematics, 2013, 27(3): 1527-1543.

DOI：10.1137/100819540

• approximation algorithms
• network design
• power assignment
• greedy algorithm
• submodular function

Given a directed simple graph G = (V, E) and a cost function c : E -> R+, the power of a vertex u in a directed spanning subgraph H is given by pH(u) = max(uv is an element of E(H)) c(uv), and corresponds to the energy consumption required for wireless node u to transmit to all nodes v with uv is an element of E(H). The power of H is given by p(H) = Sigma(u is an element of V) p(H)(u). Power Assignment seeks to minimize p(H) while H satisfies some connectivity constraint. In this paper, we assume E is bidirected (for every directed edge e is an element of E, the opposite edge exists and has the same cost), while H is required to be strongly connected. This is the original power assignment problem introduced by Chen and Huang in 1989, who proved that a bidirected minimum spanning tree has approximation ratio at most 2 (this is tight). In 2010, we introduced a greedy approximation algorithm and claimed a ratio of 1.992. Here we improve the algorithm's analysis to 1.85, combining techniques from Robins and Zelikovsky in 2000 for Steiner Tree, and Caragiannis, Flammini, and Moscardelli in 2007 for the broadcast version of Power Assignment, together with a simple idea inspired by Byrka and coworkers in 2010. The proof also shows that a natural linear programming relaxation, introduced by Calinescu and Qiao in 2012, has integrality gap at most 1.85.

• 出版日期2013