Exact ratio preservation via outliers for fair $k$-center clustering
2026-07-06 • Data Structures and Algorithms
Data Structures and Algorithms
AI summaryⓘ
The authors study how to group items into clusters while making sure each cluster has exactly the right mix of different groups, even if the whole dataset doesn’t have those exact proportions. They build on earlier fair clustering methods by allowing some points to be treated as outliers to achieve precise group ratios. Their approach works for any number of groups and can find solutions that are close to the best possible. They also tested their methods practically and compared different versions to show it can work well in real situations.
k-center clusteringdemographic fairnessfair clusteringoutliersproportion constraintsapproximation algorithmsgroup fairnesscombinatorial optimizationNeurIPS 2017
Authors
Anna Arutyunova, Irina Fast, Annika Hennes, Carsten Krollmann, Daniel R. Schmidt, Melanie Schmidt
Abstract
We study the $k$-center clustering problem under demographic fairness constraints, where the point set is partitioned into groups, and the aim is to compute clusters that exhibit a given group proportion. Previous work in this direction assumes that the entire point set already respects the desired proportions or uses relaxed notions of fairness. In this work, we propose a model that facilitates the creation of clusters that exactly match given target ratios, even when the input point set does not. We combine the well-known fair clustering model initiated by Chierichetti, Kumar, Lattanzi, and Vassilvitskii (NeurIPS 2017) with the notion of outliers to obtain a practical combinatorial framework that provides constant-factor approximate solutions for all proportion settings from $1:1$ for two groups to $t_1:t_2:\ldots:t_m$ for $m\geq 2$ groups, where $t_1,\ldots,t_m$ are integers. We implement and evaluate our algorithms, compare different variants, and provide evidence of the practicability of this approach.