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(kln⁡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^⁎=max_v∈V⁡p_v is the maximum bonus. In particular, for the most natural case p^⁎=1 we improve the ratio from O(kln⁡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 [4]. 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.