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., 2001) to 3+ϵ, which matches the current best approximation factor for the k‐median problem.
