Approximating source location and star survivable network problems

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 d_v of v. In many SL problems ψ(S, v) = d_v 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” p_v ≤ d_v, and ψ(S, v) = p_v + κ(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 = max_v∈V d_v 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^∗ = ma_xv∈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(ln² 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, ln² k}) for this variant, improving over the best ratio known for the general case O(k³ 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 {b_v: v ∈ V }, and require that the minimum cost of a flow of value d_v from S to every node v is at most b_v.