Tight Analysis of a Multiple-Swap Heuristic for Budgeted Red-Blue Median

Zachary Friggstad, Yifeng Zhang

Budgeted Red-Blue Median is a generalization of classic $k$-Median in that there are two sets of facilities, say $\mathcal{R}$ and $\mathcal{B}$, that can be used to serve clients…