Approximating Minimum‐Power Degree and Connectivity Problems

Power optimization is a central issue in wireless network design. Given a graph with costs on the edges, the power of a node is the maximum cost of an edge incident to it, and the power of a graph is the sum of the powers of its nodes. Motivated by applications in wireless networks, we consider several fundamental undirected network design problems under the power minimization criteria. Given a graph $𝒢=(V,ℰ)$ with edge costs {c(e):e∈ℰ} and degree requirements {r(v):v∈V}, the Minimum-Power Edge-Multi-Cover (MPEMC) problem is to find a minimum‐power subgraph G of $𝒢$ so that the degree of every node v in G is at least r(v). We give an O(log n)‐approximation algorithms for MPEMC , improving the previous ratio O(log ⁴ n). This is used to derive an O(log n+α)‐approximation algorithm for the undirected Minimum-Power k -Connected Subgraph (MPkCS) problem, where α is the best known ratio for the min‐cost variant of the problem. Currently, $\alpha =O(\log k\cdot \log \frac{n}{n‐k})$ which is O(log k) unless k=n-o(n), and is O(log ² k)=O(log ² n) for k=n-o(n). Our result shows that the min‐power and the min‐cost versions of the problem are equivalent with respect to approximation, unless the min‐cost variant admits an o(log n)‐approximation, which seems to be out of reach at the moment.