Approximating minimum-power edge-covers and 2,32,3-connectivity

Given a graph with edge costs, the power of a node is the maximum cost of an edge leaving 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. The Minimum-Power Edge-Cover (MPEC) problem is: given a graph G=(V,E)G=(V,E) with edge costs {c(e):e∈E}{c(e):e∈E} and a subset S⊆VS⊆V of nodes, find a minimum-power subgraph HH of GG containing an edge incident to every node in SS. We give a 3/2-approximation algorithm for MPEC, improving over the 2-approximation by [M.T. Hajiaghayi, G. Kortsarz, V.S. Mirrokni, Z. Nutov, Power optimization for connectivity problems, Mathematical Programming 110 (1) (2007) 195–208]. For the Min-Powerkk-Connected Subgraph (MPkCS) problem we obtain the following results. For k=2k=2 and k=3k=3, we improve the previously best known ratios of 4 [G. Calinescu, P.J. Wan, Range assignment for biconnectivity and kk-edge connectivity in wireless ad hoc networks, Mobile Networks and Applications 11 (2) (2006) 121–128] and 7 [M.T. Hajiaghayi, G. Kortsarz, V.S. Mirrokni, Z. Nutov, Power optimization for connectivity problems, Mathematical Programming 110 (1) (2007) 195–208] to 323 and 523, respectively. Finally, we give a 4rmax4rmax-approximation algorithm for the Minimum-Power Steiner Network (MPSN) problem: find a minimum-power subgraph that contains r(u,v)r(u,v) pairwise edge-disjoint paths for every pair u,vu,v of nodes.