Approximating Source Location and Star Survivable Network Problems

In Source Location (SL) problems the goal is to select a mini-mum cost source set $S\subseteq V$ such that the connectivity (or flow) $\psi (S,v)$ from $S$ to any node $v$ is at least the demand $d_v$ of $v$. In many SL problems $\psi (S,v)=d_v$ if $v\in S$, namely, the demand of nodes selected to $S$ is completely satisfied. In a node-connectivity variant suggested recently by Fukunaga, every node $v$ gets a “bonus” $p_v\le d_v$ if it is selected to $S$. Fukunaga showed that for undirected graphs one can achieve ratio $O(k \ln k)$forhisvariant,where$k=\max_{v \in V}d_v$ is the maximum demand. We improve this by achieving ratio $\min \{p^{\ast }\text{lnk},k\}\cdot O(\ln (k\mathrm{/}{q}^{\ast }))$ for a more general version with node capacities, where $p^{\ast }={\max }_{v\in V}{p}_v$ is the maximum bonus and $q^{\ast }={\min }_{v\in V}{q}_v$ is the minimum capacity. In particular, for the most natural case $p^{\ast }=1$ considered by Fukunaga, we improve the ratio from $O(k\ln k)$ to $O({\ln }^{2}k)$. We also get ratio $O(k)$ for the edge-connectivity version, for which no ratio that depends on $k$ only was known before. 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 give 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.