In this paper, we consider the following red-blue median problem which is a generalization of the well-studied k-median problem. The input consists of a set of red facilities, a set of blue facilities, and a set of clients in a metric space and two integers k r ,k b ≥0. The problem is to open at most k r red facilities and at most k b blue facilities and minimize the sum of distances of clients to their respective closest open facilities.
We show, somewhat surprisingly, that the following simple local search algorithm yields a constant factor approximation for this problem. Start by opening any k r red and k b blue facilities. While possible, decrease the cost of the solution by closing a pair of red and blue facilities and opening a pair of red and blue facilities.
We also improve the approximation factor for the prize-collecting k-median problem from 4 (Charikar et al. in Proceedings of the ACM-SIAM Symposium on Discrete Algorithms, pp. 642–641, 2001) to 3+ϵ, which matches the current best approximation factor for the k-median problem.