2011/07/25 by Nachshon Cohen, Cohen, Nachshon, Zeev Nutov +1
Computer Science · #Data Structures and Algorithms (cs.DS) #FOS: Computer and information sciences #cs.DS
paper · pdf · doi:10.48550/arxiv.1107.4893
arxiv created 2011/07/25 · arxiv updated 2011/07/26
Given a graph with edge costs, the \em power of a node is themaximum 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 in wireless network design. Given a graph G=(V,E) with edge costs and degree bounds \r(v):v ∈ V\, the \sf Minimum-Power Edge-Multi-Cover (\sf MPEMC) 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). We give two approximation algorithms for \sf MPEMC, with ratios O(log k) and k+1/2, where k=maxv ∈ V r(v) is the maximum degree bound. This improves the previous ratios O(log n) and k+1, and implies ratios O(log k) for the \sf Minimum-Power k-Outconnected Subgraph and O(log k log (n)/(n-k)) for the \sf Minimum-Power k-Connected Subgraph problems; the latter is the currently best known ratio for the min-cost version of the problem.