Approximating minimum power covers of intersecting families and directed connectivity problems

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

תקציר

Given a (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 the graph is the sum of the powers of its nodes. Motivated by applications for wireless networks, we consider fundamental directed connectivity network design problems under the power minimization criteria: the k-outconnected and the k-connected spanning subgraph problems. For k = 1 these problems are at least as hard as the Set-Cover problem and thus have an Ω(ln |V|) approximation threshold, while for arbitrary k a polylogarithmic approximation algorithm is unlikely. We give an O(ln |V|)-approximation algorithm for any constant k. In fact, our results are based on a much more general O(ln |V|)-approximation algorithm for the problem of finding a min-power edge-cover of an intersecting set-family; a set-family F on a groundset V is intersecting if X ∩ Y, X ∪ Y ∈ F for any intersecting X, Y ∈ F, and an edge set I covers F if for every X ∈ F there is an edge in I entering X.

שפה מקוריתאנגלית
כותר פרסום המארחApproximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques - 9th International Workshop on Approximation Algorithms for Combinatorial Optimization Problems, APPROX 2006 a
מוציא לאורSpringer Verlag
עמודים236-247
מספר עמודים12
מסת"ב (מודפס)3540380442, 9783540380443
מזהי עצם דיגיטלי (DOIs)
סטטוס פרסוםפורסם - 2006
אירוע9th International Workshop on Approximation Algorithms for Combinatorial Optimization Problems, APPROX 2006 and 10th International Workshop on Randomization and Computation, RANDOM 2006 - Barcelona, ספרד
משך הזמן: 28 אוג׳ 200630 אוג׳ 2006

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

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

כנס

כנס9th International Workshop on Approximation Algorithms for Combinatorial Optimization Problems, APPROX 2006 and 10th International Workshop on Randomization and Computation, RANDOM 2006
מדינה/אזורספרד
עירBarcelona
תקופה28/08/0630/08/06

טביעת אצבע

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

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