Power optimization for connectivity problems

Mohammad T. Hajiaghayi, Guy Kortsarz, Vahab S. Mirrokni, Zeev Nutov

פרסום מחקרי: פרסום בכתב עתמאמר מכנסביקורת עמיתים


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.

שפה מקוריתאנגלית
עמודים (מ-עד)349-361
מספר עמודים13
כתב עתLecture Notes in Computer Science
מזהי עצם דיגיטלי (DOIs)
סטטוס פרסוםפורסם - 2005
אירוע11th International IPCO Conference on Integer Programming and Combinatorial Optimization - Berlin, גרמניה
משך הזמן: 8 יוני 200510 יוני 2005

טביעת אצבע

להלן מוצגים תחומי המחקר של הפרסום 'Power optimization for connectivity problems'. יחד הם יוצרים טביעת אצבע ייחודית.

פורמט ציטוט ביבליוגרפי