Red–Blue k -Center Clustering with Distance Constraints.

We consider a variant of the k-center clustering problem in I R d , where the centers can be divided into two subsets—one, the red centers of size p, and the other, the blue centers of size q, such that p + q = k , and each red center and each blue center must be a distance of at least some given α ≥ 0 apart. The aim is to minimize the covering radius. We provide a bi-criteria approximation algorithm for the problem and a polynomial time algorithm for the constrained problem where all centers must lie on a given line ℓ. Additionally, we present a polynomial time algorithm for the case where only the orientation of the line is fixed in the plane ( d = 2 ), although the algorithm works even in I R d by constraining the line to lie in a plane and with a fixed orientation. [ABSTRACT FROM AUTHOR]