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 (possibly directed) graph with costs on the edges, the power of a node is the maximum cost of an edge leaving 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 with edge costs and degree requirements {r(v):v ∈ V}, the Minimum-Power Edge-Multi-Cover ( ) problem is to find a minimum-power subgraph of so that the degree of every node v is at least r(v). We give an O(logn)-approximation algorithms for , improving the previous ratio O(log4 n) of [11]. This is used to derive an O(logn + α)-approximation algorithm for the undirected Minimum-Power k -Connected Subgraph ( ) problem, where is the best known ratio for the min-cost variant of the problem (currently, = O(In k) for n ≥ 2k2 and otherwise). Surprisingly, it 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(logn)-approximation, which seems to be out of reach at the moment. We also improve the best known approximation ratios for small requirements. Specifically, we give a 3/2-approximation algorithm for with r(v) ∈ {0,1}, improving over the 2-approximation by [11], and a -approximation for the minimum-power 2-Connected and 2-Edge-Connected Subgraph problems, improving the 4-approximation by [4]. Finally, we give a 4 r max -approximation algorithm for the undirected Minimum-Power Steiner Network ( ) problem: find a minimum-power subgraph that contains r(u,v) pairwise edge-disjoint paths for every pair u,v of nodes.

שפה מקוריתאנגלית
כותר פרסום המארחLATIN 2008
כותר משנה של פרסום המארחTheoretical Informatics - 8th Latin American Symposium, Proceedings
מוציא לאורSpringer Verlag
עמודים423-435
מספר עמודים13
מסת"ב (מודפס)3540787720, 9783540787723
מזהי עצם דיגיטלי (DOIs)
סטטוס פרסוםפורסם - 2008
אירוע8th Latin American Theoretical INformatics Symposium, LATIN 2008 - Buzios, ברזיל
משך הזמן: 7 אפר׳ 200811 אפר׳ 2008

סדרות פרסומים

שםLecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)
כרך4957 LNCS
ISSN (מודפס)0302-9743
ISSN (אלקטרוני)1611-3349

כנס

כנס8th Latin American Theoretical INformatics Symposium, LATIN 2008
מדינה/אזורברזיל
עירBuzios
תקופה7/04/0811/04/08

טביעת אצבע

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

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