Approximating minimum power edge-multi-covers

Given an undirected graph with edge costs, 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 the following fundamental problem that arises in wireless network design. Given a graph $$G=(V,E)$$ G = ( V , E ) with edge costs and lower degree bounds $$\{r(v):v \in V\}$$ { r ( v ) : v ∈ V } , the Min-Power Edge-Multicover problem is to find a minimum-power subgraph $$J$$ J of $$G$$ G such that the degree of every node $$v$$ v in $$J$$ J is at least $$r(v)$$ r ( v ) . Let $$k=\max _{v \in V} r(v)$$ k = max v ∈ V r ( v ) . For $$k=\Omega (\log n)$$ k = Ω ( log n ) , the previous best approximation ratio for the problem was $$O(\log n)$$ O ( log n ) , even for uniform costs (Kortsarz et al. 2011). Our main result improves this ratio to $$O(\log k)$$ O ( log k ) for general costs, and to $$O(1)$$ O ( 1 ) for uniform costs. This also implies ratios $$O(\log k)$$ O ( log k ) for the Min-Power $$k$$ k -Outconnected Subgraph and $$O\left( \log k \log \frac{n}{n-k} \right) $$ O log k log n n - k for the Min-Power $$k$$ k -Connected Subgraph problems; the latter is the currently best known ratio for the min-cost version of the problem when $$n \le k{(k-1)}^2$$ n ≤ k ( k - 1 ) 2 . In addition, for small values of $$k$$ k , we improve the previously best ratio $$k+1$$ k + 1 to $$k+1/2$$ k + 1 / 2 .