A simple greedy approximation algorithm for the minimum connected k-Center problem

In this paper, we consider the connected (Formula presented.) -Center ((Formula presented.)) problem, which can be seen as the classic (Formula presented.) -Center problem with the constraint of internal connectedness, i.e., two nodes in a cluster are required to be connected by an internal path in the same cluster. (Formula presented.) was first introduced by Ge et al. (ACM Trans Knowl Discov Data 2:7, 2008), in which they showed the (Formula presented.) -completeness for this problem and claimed a polynomial time approximation algorithm for it. However, the running time of their algorithm might not be polynomial, as one key step of their algorithm involves the computation of an (Formula presented.) -hard problem. We first present a simple polynomial time greedy-based (Formula presented.) -approximation algorithm for the relaxation of (Formula presented.) —the (Formula presented.). Further, we give a (Formula presented.) -approximation algorithm for (Formula presented.).