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.

错误:搜索内容不能为空,请输入英文关键词
错误:关键词超出字数限制,请精简
高级检索

Fair \( k \) -Center Clustering with Minimum Representation Guarantees

  • Meiyun Lu,
  • Longkun Guo

摘要

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.