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) with edge costs and lower degree bounds {r(v):v∈V}, the Min-Power Edge-Multicover problem is to find a minimum-power subgraph J of G such that the degree of every node v in J is at least r(v). Let k=maxv∈Vr(v). For k=Ω(logn), the previous best approximation ratio for the problem was O(logn), even for uniform costs (Kortsarz et al. 2011). Our main result improves this ratio to O(logk) for general costs, and to O(1) for uniform costs. This also implies ratios O(logk) for the Min-Power k-Outconnected Subgraph and Ologklognn-k for the Min-Power k-Connected Subgraph problems; the latter is the currently best known ratio for the min-cost version of the problem when n≤k^(k-1)2. In addition, for small values of k, we improve the previously best ratio k+1 to k+1/2.