2026-08-25T18:47:23Z https://drops.dagstuhl.de/oai

oai:drops-oai.dagstuhl.de:27159 2026-08-25T13:18:16Z ddc:004 open_access

Exact Ratio Preservation via Outliers for Fair k-Center Clustering Arutyunova, Anna Fast, Irina Hennes, Annika Krollmann, Carsten Schmidt, Daniel R. Schmidt, Melanie Fairness k-center approximation algorithms 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 [Flavio Chierichetti et al., 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₁:t₂:…:t_m for m ≥ 2 groups, where t₁,…,t_m are integers. We implement and evaluate our algorithms, compare different variants, and provide evidence of the practicability of this approach. Schloss Dagstuhl – Leibniz-Zentrum für Informatik Anna Arutyunova and Irina Fast and Annika Hennes and Carsten Krollmann and Daniel R. Schmidt and Melanie Schmidt 2026 Is Part Of LIPIcs, Volume 388, 34th Annual European Symposium on Algorithms (ESA 2026) InProceedings Text doc-type:ResearchArticle publishedVersion application/pdf doi:10.4230/LIPIcs.ESA.2026.23 urn:nbn:de:0030-drops-271592 https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ESA.2026.23 eng https://creativecommons.org/licenses/by/4.0/legalcode