Constant-Factor Approximations for Doubly Constrained Fair k k -Center, k k -Median and k k -Means
Nicole Funk, Annika Hennes, Johanna Hillebrand, Sarah Sturm · 2026
Read Constant-Factor Approximations for Doubly Constrained Fair k k -Center, k k -Median and k k -Means by Nicole Funk, Annika Hennes, Johanna Hillebrand, Sarah Sturm (2026) in the Tower of Babel, a free online library of public-domain works preserved in clean, searchable text. No sign-up. The full text is served as a plain-text file at a predictable URL, where text is present: https://antarctic-labs.com/tower-of-babel/arxiv-2604-16061.txt.
Description
Funk and three colleagues study discrete k-clustering in metric spaces under two fairness rules: even traits within clusters, and even center members from each attribute. Prior work stays within 8 times the best, with small gap. For k-center, they improve this to 4 times the best, with small additive gap. For k-median and k-means, they give the first constant-factor methods. They convert a diverse pick into a fair grouping via linear methods, extending to matroid and knapsack constraints.
Catalog record
| CREATOR | Nicole Funk, Annika Hennes, Johanna Hillebrand, Sarah Sturm |
|---|---|
| YEAR | 2026 |
| COLLECTION | PAPERS |
| FORMAT | TXT |
| FILE SIZE | 82804 |
| LICENSE | http://creativecommons.org/licenses/by/4.0/ |
| RIGHTS | CC BY |
| SOURCE | arXiv |
Source: https://arxiv.org/abs/2604.16061