Approximating minimum cost source location problems with local vertex-connectivity demands

In the source location problem, the goal is to compute a minimum cost source set in a graph so that the connectivity between the source set and each vertex is at least the demand of the vertex. In this paper, we consider the problem for undirected graphs, and the connectivity between a source set S and a vertex v is defined as the maximum number of paths between v and S no two of which have common vertex except v  . We give an O(d⁎logd⁎)-approximation algorithm for the problem with maximum demand d⁎d⁎. We also define a variant of the source location problem and give an approximation algorithm for it.