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.