## Abstract

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 Θ(lnd(V)) in [20], for his variant on undirected graphs Fukunaga achieved ratio O(klnk), where k=max_{v∈V}d_{v} is the maximum demand. We improve this by achieving ratio min{p^{⁎}lnk,k}⋅O(lnk) 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(klnk) 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{lnn,ln^{2}k}) for this variant, improving over the best ratio known for the general case O(k^{3}lnn) 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}.

Original language | English (US) |
---|---|

Pages (from-to) | 32-42 |

Number of pages | 11 |

Journal | Theoretical Computer Science |

Volume | 674 |

DOIs | |

State | Published - Apr 25 2017 |

## All Science Journal Classification (ASJC) codes

- Theoretical Computer Science
- Computer Science(all)

## Keywords

- Source location
- Submodular cover
- Survivable network