Greedy approximation for the source location problem with vertex-connectivity requirements in undirected graphs

Let $G=(V,E)$ be a simple undirected graph with a set V of vertices and a set E of edges. Each vertex $v\in V$ has a demand $d(v)\in Z_{+}$, and a cost $c(v)\in R_{+}$, where $Z_{+}$ and $R_{+}$ denote the set of nonnegative integers and the set of nonnegative reals, respectively. The source location problem with vertex-connectivity requirements in a given graph G asks to find a set S of vertices minimizing ${\sum }_{v\in S}c(v)$ such that there are at least $d(v)$ pairwise vertex-disjoint paths from S to v for each vertex $v\in V?S$. It is known that the problem is not approximable within a ratio of $O(\ln {\sum }_{v\in V}d(v))$, unless NP has an $O(N^{\log \log N})$-time deterministic algorithm. Also, it is known that even if every vertex has a uniform cost and $d^1=4$ holds, then the problem is NP-hard, where $d^1=\max \{d(v)|v\in V\}$.In this paper, we consider the problem in the case where every vertex has uniform cost. We propose a simple greedy algorithm for providing a $\max \{d^1,2d^1?6\}$-approximate solution to the problem in $O(\min \{d^1,\sqrt{|V|}\}{d}^1{|V|}^2)$ time, while we also show that there exists an instance for which it provides no better than a $(d^1?1)$-approximate solution. Especially, in the case of $d^1?4$, we give a tight analysis to show that it achieves an approximation ratio of 3. We also show the APX-hardness of the problem even restricted to $d^1?4$.