תקציר
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 |
מזהי עצם דיגיטלי (DOIs) | |
סטטוס פרסום | פורסם - 2016 |
אירוע | 41st International Workshop on Graph-Theoretic Concepts in Computer Science, WG 2015 - Garching, גרמניה משך הזמן: 17 יוני 2015 → 19 יוני 2015 |
סדרות פרסומים
שם | Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics) |
---|---|
כרך | 9224 LNCS |
ISSN (מודפס) | 0302-9743 |
ISSN (אלקטרוני) | 1611-3349 |
כנס
כנס | 41st International Workshop on Graph-Theoretic Concepts in Computer Science, WG 2015 |
---|---|
מדינה/אזור | גרמניה |
עיר | Garching |
תקופה | 17/06/15 → 19/06/15 |
הערה ביבליוגרפית
Publisher Copyright:© Springer International Publishing Switzerland 2016.