TY - JOUR
T1 - Power optimization for connectivity problems
AU - Hajiaghayi, Mohammad T.
AU - Kortsarz, Guy
AU - Mirrokni, Vahab S.
AU - Nutov, Zeev
PY - 2005
Y1 - 2005
N2 - Given a graph with costs on the edges, the power of a node is the maximum cost of an edge leaving it, and the power of the graph is the sum of the powers of the nodes of this graph. Motivated by applications in wireless multi-hop networks, we consider four fundamental problems under the power minimization criteria: the Min-Power b-Edge-Cover problem (MPb-EC) where the goal is to find a min-power subgraph so that the degree of every node v is at least some given integer b(v), the Min-Power k-node Connected Spanning Subgraph problem (MP k-CSS), Min-Power k-edge Connected Spanning Subgraph problem (MP k-ECSS), and finally the Min-Power k-Edge-Disjoint Paths problem in directed graphs (MP k-EDP). We give an O(log4 n)-approximation algorithm for MPb-EC. This gives an O(log4 n)-approximation algorithm for MP k-CSS for most values of k, improving the best previously known O(k)-approximation guarantee. In contrast, we obtain an O(√n) approximation algorithm for MP k-ECSS, and for its variant in directed graphs (i.e., MP k-EDP), we establish the following inapproximability threshold: MP k-EDP cannot be approximated within O(2 log 1-ε n) for any fixed ε > 0, unless NP-hard problems can be solved in quasi-polynomial time.
AB - Given a graph with costs on the edges, the power of a node is the maximum cost of an edge leaving it, and the power of the graph is the sum of the powers of the nodes of this graph. Motivated by applications in wireless multi-hop networks, we consider four fundamental problems under the power minimization criteria: the Min-Power b-Edge-Cover problem (MPb-EC) where the goal is to find a min-power subgraph so that the degree of every node v is at least some given integer b(v), the Min-Power k-node Connected Spanning Subgraph problem (MP k-CSS), Min-Power k-edge Connected Spanning Subgraph problem (MP k-ECSS), and finally the Min-Power k-Edge-Disjoint Paths problem in directed graphs (MP k-EDP). We give an O(log4 n)-approximation algorithm for MPb-EC. This gives an O(log4 n)-approximation algorithm for MP k-CSS for most values of k, improving the best previously known O(k)-approximation guarantee. In contrast, we obtain an O(√n) approximation algorithm for MP k-ECSS, and for its variant in directed graphs (i.e., MP k-EDP), we establish the following inapproximability threshold: MP k-EDP cannot be approximated within O(2 log 1-ε n) for any fixed ε > 0, unless NP-hard problems can be solved in quasi-polynomial time.
UR - http://www.scopus.com/inward/record.url?scp=24944538657&partnerID=8YFLogxK
U2 - 10.1007/11496915_26
DO - 10.1007/11496915_26
M3 - ???researchoutput.researchoutputtypes.contributiontojournal.conferencearticle???
AN - SCOPUS:24944538657
SN - 0302-9743
VL - 3509
SP - 349
EP - 361
JO - Lecture Notes in Computer Science
JF - Lecture Notes in Computer Science
T2 - 11th International IPCO Conference on Integer Programming and Combinatorial Optimization
Y2 - 8 June 2005 through 10 June 2005
ER -