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
المعرِّفات الرقمية للأشياء
حالة النشرنُشِر - 2008
الحدث8th Latin American TheoreticalINformatics Symposium, LATIN 2008 - Buzios, البرازيل
المدة: ٧ أبريل ٢٠٠٨١١ أبريل ٢٠٠٨

سلسلة المنشورات

الاسمLecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)
مستوى الصوت4957 LNCS
رقم المعيار الدولي للدوريات (المطبوع)0302-9743
رقم المعيار الدولي للدوريات (الإلكتروني)1611-3349


!!Conference8th Latin American TheoreticalINformatics Symposium, LATIN 2008


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

قم بذكر هذا