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

CREATORNicole Funk, Annika Hennes, Johanna Hillebrand, Sarah Sturm
YEAR2026
COLLECTIONPAPERS
FORMATTXT
FILE SIZE82804
LICENSEhttp://creativecommons.org/licenses/by/4.0/
RIGHTSCC BY
SOURCEarXiv

Source: https://arxiv.org/abs/2604.16061

Browse the full library · About the Tower of Babel