Red–Blue k-Center Clustering with Distance Constraints

We consider a variant of the k-center clustering problem in IRd, where the centers can bedivided into two subsets—one, the red centers of size p, and the other, the blue centers of size q, suchthat p + q = k, and each red center and each blue center must be a distance of at least some givena ? 0 apart. The aim is to minimize the covering radius. We provide a bi-criteria approximationalgorithm for the problem and a polynomial time algorithm for the constrained problem where allcenters must lie on a given line `. Additionally, we present a polynomial time algorithm for the casewhere only the orientation of the line is fixed in the plane (d = 2), although the algorithm works evenin IRd by constraining the line to lie in a plane and with a fixed orientation