Approximating minimum-power edge-covers and 2, 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) with edge costs {c(e) : e is an element of E) and a subset S subset of V of nodes, find a minimum-power subgraph H of G containing an edge incident to every node in S. 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-Power k-Connected Subgraph (MPkCS) problem we obtain the following results. For k = 2 and k = 3, we improve the previously best known ratios of 4[G. Calinescu, P.J. Wan, Range assignment for biconnectivity and k-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 32/3 and 52/3, respectively. Finally, we give a 4r(max)-approximation algorithm for the Minimum-Power Steiner Network (MPSN) problem: find a minimum-power subgraph that contains r(u, v) pairwise edge-disjoint paths for every pair u, v of nodes.