Approximating steiner networks with node-weights

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


The (undirected) Steiner Network problem is as follows: given a graph G = (V, E) with edge/node-weights and edge-connectivity requirements {r(u,v): u,v ∈ U C 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 [Combinatorial, 21 (2001), pp. 39-60], 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 (NWSN) problem, nontrivial approximation algorithms were known only for 0, 1 requirements. We make an attempt to change this situation by giving the first nontrivial approximation algorithm for NWSN with arbitrary requirements. Our approximation ratio for NWSN is rmax · O(In |U|), where rmax = maxu,v ∈U r(u, v). This generalizes the result of Klein and Ravi [J. Algorithms, 19 (1995), pp. 104-115] for the case rmax = 1. We also give an O(In |U|)-approximation algorithm for the node-connectivity variant of NWSN (when the paths are required to be internally disjoint) for the case rmax = 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. Finally, we give evidence that a polylogarithmic approximation ratio for NWSN with large rmax might not exist even for |U| = 2 and unit weights.

שפה מקוריתאנגלית
עמודים (מ-עד)3001-3022
מספר עמודים22
כתב עתSIAM Journal on Computing
מספר גיליון7
מזהי עצם דיגיטלי (DOIs)
סטטוס פרסוםפורסם - 2010

טביעת אצבע

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

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