{"ID":5936948,"CreatedAt":"2026-07-07T03:14:33.014478982Z","UpdatedAt":"2026-07-09T17:19:04.856114502Z","DeletedAt":null,"paper_url":"https://arxiv.org/abs/2607.05342","arxiv_id":"2607.05342","title":"Exact ratio preservation via outliers for fair $k$-center clustering","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.","short_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...","url_abs":"https://arxiv.org/abs/2607.05342","url_pdf":"https://arxiv.org/pdf/2607.05342v1","authors":"[\"Anna Arutyunova\",\"Irina Fast\",\"Annika Hennes\",\"Carsten Krollmann\",\"Daniel R. Schmidt\",\"Melanie Schmidt\"]","published":"2026-07-06T17:23:55Z","proceeding":"cs.DS","tasks":"[\"cs.DS\"]","methods":"[]","has_code":false}