Approximating source location and star survivable network problems

Guy Kortsarz, Zeev Nutov

نتاج البحث: فصل من :كتاب / تقرير / مؤتمرمنشور من مؤتمرمراجعة النظراء


In Source Location (SL) problems the goal is to select a minimum cost source set S ⊆ V such that the connectivity (or flow) ψ(S, v) from S to any node v is at least the demand dv of v. In many SL problems ψ(S, v) = dv if v ∈ S, so the demand of nodes selected to S is completely satisfied. In a variant suggested recently by Fukunaga [7], every node v selected to S gets a “bonus” pv ≤ dv, and ψ(S, v) = pv + κ(S \ {v}, v) if v ∈ S and ψ(S, v) = κ(S, v) otherwise, where κ(S, v) is the maximum number of internally disjoint (S, v)-paths. While the approximability of many SL problems was seemingly settled to Θ(ln d(V )) in [20], for his variant on undirected graphs Fukunaga achieved ratio O(k ln k), where k = maxvV dv is the maximum demand. We improve this by achieving ratio min{p ln k, k} · O(ln k) for a more general version with node capacities, where p = maxv∈V pv is the maximum bonus. In particular, for the most natural case p = 1 we improve the ratio from O(k ln k) to O(ln2 k). To derive these results, we consider a particular case of the Survivable Network (SN) problem when all edges of positive cost form a star. We obtain ratio O(min{ln n, ln2 k}) for this variant, improving over the best ratio known for the general case O(k3 ln n) of Chuzhoy and Khanna [3]. In addition, we show that directed SL with unit costs is Ω(log n)-hard to approximate even for 0, 1 demands, while SL with uniform demands can be solved in polynomial time. Finally, we obtain a logarithmic ratio for a generalization of SL where we also have edge-costs and flow-cost bounds {bv: v ∈ V }, and require that the minimum cost of a flow of value dv from S to every node v is at most bv.

اللغة الأصليةالإنجليزيّة
عنوان منشور المضيفGraph-Theoretic Concepts in Computer Science - 41st International Workshop, WG 2015, Revised Papers
المحررونErnst W. Mayr
ناشرSpringer Verlag
عدد الصفحات16
رقم المعيار الدولي للكتب (المطبوع)9783662531730
المعرِّفات الرقمية للأشياء
حالة النشرنُشِر - 2016
الحدث41st International Workshop on Graph-Theoretic Concepts in Computer Science, WG 2015 - Garching, ألمانيا
المدة: ١٧ يونيو ٢٠١٥١٩ يونيو ٢٠١٥

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

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


!!Conference41st International Workshop on Graph-Theoretic Concepts in Computer Science, WG 2015

ملاحظة ببليوغرافية

Publisher Copyright:
© Springer International Publishing Switzerland 2016.


أدرس بدقة موضوعات البحث “Approximating source location and star survivable network problems'. فهما يشكلان معًا بصمة فريدة.

قم بذكر هذا