DROPS

Document

DOI: 10.4230/LIPIcs.ESA.2026.23

Exact Ratio Preservation via Outliers for Fair k-Center Clustering

Authors: Anna Arutyunova, Irina Fast, Annika Hennes, Carsten Krollmann, Daniel R. Schmidt, and Melanie Schmidt

Published in: LIPIcs, Volume 388, 34th Annual European Symposium on Algorithms (ESA 2026)

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 [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.

Cite as

Anna Arutyunova, Irina Fast, Annika Hennes, Carsten Krollmann, Daniel R. Schmidt, and Melanie Schmidt. Exact Ratio Preservation via Outliers for Fair k-Center Clustering. In 34th Annual European Symposium on Algorithms (ESA 2026). Leibniz International Proceedings in Informatics (LIPIcs), Volume 388, pp. 23:1-23:23, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2026)

Copy BibTex To Clipboard

@InProceedings{arutyunova_et_al:LIPIcs.ESA.2026.23,
  author =	{Arutyunova, Anna and Fast, Irina and Hennes, Annika and Krollmann, Carsten and Schmidt, Daniel R. and Schmidt, Melanie},
  title =	{{Exact Ratio Preservation via Outliers for Fair k-Center Clustering}},
  booktitle =	{34th Annual European Symposium on Algorithms (ESA 2026)},
  pages =	{23:1--23:23},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-445-1},
  ISSN =	{1868-8969},
  year =	{2026},
  volume =	{388},
  editor =	{Bille, Philip and Pettie, Seth and Storandt, Sabine},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ESA.2026.23},
  URN =		{urn:nbn:de:0030-drops-271592},
  doi =		{10.4230/LIPIcs.ESA.2026.23},
  annote =	{Keywords: Fairness, k-center, approximation algorithms}
}

Search Results

Documents authored by Krollmann, Carsten

Exact Ratio Preservation via Outliers for Fair k-Center Clustering

Abstract

Cite as

Thanks for your feedback!

Could not send message