Article ID | Journal | Published Year | Pages | File Type |
---|---|---|---|---|
4952104 | Theoretical Computer Science | 2017 | 11 Pages |
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 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.
Keywords
Related Topics
Physical Sciences and Engineering
Computer Science
Computational Theory and Mathematics
Authors
Guy Kortsarz, Zeev Nutov,