Approximating minimum-power k-connectivity

The Minimum-Power k -Connected Subgraph (MP k CS) problem seeks a power (range) assignment to the nodes of a given wireless network such that the resulting communication (sub)network is k-connected and the total power is minimum. We give a new very simple approximation algorithm for this problem that significantly improves the previously best known approximation ratios. Specifically, the approximation ratios of our algorithm are: 3 (improving (3 + 2/3)) for k = 2, 4 (improving (5 + 2/3)) for k = 3, k + 3 for k ∈ {4,5} and k + 5 for k ∈ {6,7} (improving k+2⌈(k+1)/2⌈), 3(k-1) (improving 3k) for any constant k. Our results are based on a (k+1)-approximation algorithm (improving the ratio k+4) for the problem of finding a Min-Power k -Inconnected Subgraph, which is of independent interest.