Approximating steiner networks with node weights

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


The (undirected) Steiner Network problem is: given a graph G∈=∈(V,E) with edge/node weights and edge-connectivity requirements {r(u,v):u,v∈ ∈U V}, find a minimum weight subgraph H of G containing U so that the uv-edge-connectivity in H is at least r(u,v) for all u,v∈ ∈U. The seminal paper of Jain [12], and numerous papers preceding it, considered the Edge-Weighted Steiner Network problem, with weights on the edges only, and developed novel tools for approximating minimum weight edge-covers of several types of set functions and families. However, for the Node-Weighted Steiner Network ( ) problem, nontrivial approximation algorithms were known only for 0,1 requirements. We make an attempt to change this situation, by giving the first non-trivial approximation algorithm for with arbitrary requirements. Our approximation ratio for is r max •O(ln |U|), where r max ∈=∈ max u,v∈ ∈U r(u,v). This generalizes the result of Klein and Ravi [14] for the case r max =∈1. We also give an O(ln |U|)-approximation algorithm for the node-connectivity variant of (when the paths are required to be internally-disjoint) for the case r max =∈2. Our results are based on a much more general approximation algorithm for the problem of finding a minimum node-weighted edge-cover of an uncrossable set-family. We also give the first evidence that a polylogarithmic approximation ratio for might not exist even for |U|∈=∈2 and unit weights.

שפה מקוריתאנגלית
כותר פרסום המארחLATIN 2008
כותר משנה של פרסום המארחTheoretical Informatics - 8th Latin American Symposium, Proceedings
מספר עמודים12
מזהי עצם דיגיטלי (DOIs)
סטטוס פרסוםפורסם - 2008
אירוע8th Latin American TheoreticalINformatics 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 TheoreticalINformatics Symposium, LATIN 2008

טביעת אצבע

להלן מוצגים תחומי המחקר של הפרסום 'Approximating steiner networks with node weights'. יחד הם יוצרים טביעת אצבע ייחודית.

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