Approximating minimum-power degree and connectivity problems

Guy Kortsarz, Vahab S. 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 G=(V, ε) with edge costs {c(e):e ∈ε} and degree requirements {r(v):v 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+α)-approximation algorithm for the undirected {Minimum-Power k-Connected Subgraph} ({MPkCS}) problem, where α is the best known ratio for the min-cost variant of the problem. Currently, α=O(log k̇ logn/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.

שפה מקוריתאנגלית
עמודים (מ-עד)735-742
מספר עמודים8
כתב עתAlgorithmica
מספר גיליון4
מזהי עצם דיגיטלי (DOIs)
סטטוס פרסוםפורסם - אוג׳ 2011

הערה ביבליוגרפית

Funding Information:
G. Kortsarz was partially supported by NSF award number 0829959.

טביעת אצבע

להלן מוצגים תחומי המחקר של הפרסום 'Approximating minimum-power degree and connectivity problems'. יחד הם יוצרים טביעת אצבע ייחודית.

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