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
مستوى الصوت39
رقم الإصدار7
المعرِّفات الرقمية للأشياء
حالة النشرنُشِر - 2010


أدرس بدقة موضوعات البحث “Approximating steiner networks with node-weights'. فهما يشكلان معًا بصمة فريدة.

قم بذكر هذا