科研之友
微信
新浪微博
Facebook
分享链接
摘要
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 G = (V, epsilon) with edge costs {c(e) : e is an element of epsilon} and degree requirements {r(v) : v. is an element of V}, the Minimum- Power Edge-Multi-Cover (MPEMC) problem is to find a minimum-power subgraph G of 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 MPEMC, improving the previous ratio O(log(4) n). This is used to derive an O(log n alpha)- approximation algorithm for the undirected Minimum- Power k- Connected Subgraph (MPkCS) problem, where a is the best known ratio for the min- cost variant of the problem. Currently, alpha = O(log k . log 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 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.
- 出版日期2011-8
