ملخص
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 = maxv∈V 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 |
الصفحات | 203-218 |
عدد الصفحات | 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 |
!!Conference
!!Conference | 41st International Workshop on Graph-Theoretic Concepts in Computer Science, WG 2015 |
---|---|
الدولة/الإقليم | ألمانيا |
المدينة | Garching |
المدة | ١٧/٠٦/١٥ → ١٩/٠٦/١٥ |
ملاحظة ببليوغرافية
Publisher Copyright:© Springer International Publishing Switzerland 2016.