Fair \( k \) -Center Clustering with Minimum Representation Guarantees
摘要
We investigate the fair \( k \) -center clustering problem under the Minimum Representation Fairness (MR-fairness) criterion, which requires that a protected group constitutes at least half of the points in at least \( \frac{k}{2} \) of the resulting clusters. This fairness notion is motivated by applications such as electoral districting and content recommendation, where group influence relies on achieving local majorities. We present a 9-approximation algorithm for the case of two-group data that guarantees this fairness constraint. Our approach integrates greedy center selection, all-or-nothing rounding, and a bipartite matching-based reassignment strategy to ensure both coverage quality and fair representation.