caa a22 4500 445804491 CHVBK 20180317145152.0 cr unu---uuuuu 170323e20110801xx s 000 0 eng 10.1007/s00453-009-9365-5 doi (NATIONALLICENCE)springer-10.1007/s00453-009-9365-5 Approximating Minimum-Power Degree andConnectivity Problems [Elektronische Daten] [Guy Kortsarz, Vahab Mirrokni, Zeev Nutov, Elena Tsanko] Power optimization is a central issue in wireless network design. Given a graph with costs on the edges, 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 several fundamental undirected network design problems under the power minimization criteria. Given a graph $\mathcal{G}=(V,\mathcal{E})$ with edge costs {c(e):e∈ℰ} and degree requirements {r(v):v∈V}, the $\textsf{Minimum-Power Edge-Multi-Cover}$ ($\textsf{MPEMC}$ ) problem is to find a minimum-power subgraph G of $\mathcal{G}$ so that the degree of every node v in G is at least r(v). We give an O(log n)-approximation algorithms for $\textsf{MPEMC}$ , improving the previous ratio O(log 4 n). This is used to derive an O(log n+α)-approximation algorithm for the undirected $\textsf{Minimum-Power $k$-Connected Subgraph}$ ($\textsf{MP$k$CS}$ ) problem, where α is the best known ratio for the min-cost variant of the problem. Currently, $\alpha=O(\log k\cdot \log\frac{n}{n-k})$ which is O(log k) unless k=n−o(n), and is O(log 2 k)=O(log 2 n) for k=n−o(n). Our result shows that the min-power and the min-cost versions of the $\textsf{$k$-Connected Subgraph}$ problem are equivalent with respect to approximation, unless the min-cost variant admits an o(log n)-approximation, which seems to be out of reach at the moment. Springer Science+Business Media, LLC, 2009 Power nationallicence Graphs nationallicence Wireless nationallicence Degree nationallicence k -connectivity nationallicence Approximation nationallicence Kortsarz Guy Rutgers University, Camden, NJ, USA aut Mirrokni Vahab Google Research, New York, NY, USA aut Nutov Zeev The Open University of Israel, Raanana, Israel aut Tsanko Elena IBM, Haifa, Israel aut Algorithmica Springer-Verlag 60/4(2011-08-01), 735-742 0178-4617 60:4<735 2011 60 453 https://doi.org/10.1007/s00453-009-9365-5 text/html Onlinezugriff via DOI 1 research-article jats NATIONALLICENCE 856 40 https://doi.org/10.1007/s00453-009-9365-5 text/html Onlinezugriff via DOI NATIONALLICENCE 700 1- Kortsarz Guy Rutgers University, Camden, NJ, USA aut NATIONALLICENCE 700 1- Mirrokni Vahab Google Research, New York, NY, USA aut NATIONALLICENCE 700 1- Nutov Zeev The Open University of Israel, Raanana, Israel aut NATIONALLICENCE 700 1- Tsanko Elena IBM, Haifa, Israel aut NATIONALLICENCE 773 0- Algorithmica Springer-Verlag 60/4(2011-08-01), 735-742 0178-4617 60:4<735 2011 60 453 Metadata rights reserved Springer special CC-BY-NC licence nationallicence BK010053 XK010053 XK010000 NATIONALLICENCE NATIONALLICENCE NL-springer