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 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(kln⁡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(kln⁡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(k3ln⁡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 {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.