TY - GEN
T1 - Approximating minimum power edge-multi-covers
AU - Cohen, Nachshon
AU - Nutov, Zeev
N1 - Copyright:
Copyright 2012 Elsevier B.V., All rights reserved.
PY - 2012
Y1 - 2012
N2 - Given a 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 in wireless network design. Given a graph G = (V,E) with edge costs and degree bounds {r(v):v ∈ V}, the Minimum-Power Edge-Multi-Cover (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). Let k = max v ∈ V r(v). For k = Ω(logn), the previous best approximation ratio for MPEMC was O(logn), even for uniform costs [3]. 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 Minimum-Power k -Outconnected Subgraph and O(log k log n/n-k) for the Minimum-Power k -Connected Subgraph problems; the latter is the currently best known ratio for the min-cost version of the problem. In addition, for small values of k, we improve the previously best ratio k + 1 to k + 1/2.
AB - Given a 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 in wireless network design. Given a graph G = (V,E) with edge costs and degree bounds {r(v):v ∈ V}, the Minimum-Power Edge-Multi-Cover (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). Let k = max v ∈ V r(v). For k = Ω(logn), the previous best approximation ratio for MPEMC was O(logn), even for uniform costs [3]. 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 Minimum-Power k -Outconnected Subgraph and O(log k log n/n-k) for the Minimum-Power k -Connected Subgraph problems; the latter is the currently best known ratio for the min-cost version of the problem. In addition, for small values of k, we improve the previously best ratio k + 1 to k + 1/2.
UR - http://www.scopus.com/inward/record.url?scp=84865563974&partnerID=8YFLogxK
U2 - 10.1007/978-3-642-30642-6_7
DO - 10.1007/978-3-642-30642-6_7
M3 - ???researchoutput.researchoutputtypes.contributiontobookanthology.conference???
AN - SCOPUS:84865563974
SN - 9783642306419
T3 - Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)
SP - 64
EP - 75
BT - Computer Science - Theory and Applications - 7th International Computer Science Symposium in Russia, CSR 2012, Proceedings
T2 - 7th International Computer Science Symposium in Russia on Computer Science - Theory and Applications, CSR 2012
Y2 - 3 July 2012 through 7 July 2012
ER -