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 ⁎ = max v ∈ V ⁡ p v 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 2 ⁡ 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 2 ⁡ k } ) for this variant, improving over the best ratio known for the general case O ( k 3 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.

Authors

• Guy Kortsarz
• Zeev Nutov

Keywords

• Source location
• Survivable network
• Submodular cover