cs.DSApr 17, 2026

Constant-Factor Approximations for Doubly Constrained Fair k-Center, k-Median and k-Means

Authors: Nicole Funk, Annika Hennes, Johanna Hillebrand, Sarah Sturm

Organizations: Department of Informatics, University of Cologne, Germany · Heinrich Heine University Düsseldorf, Faculty of Mathematics and Natural Sciences, Germany · Department of Informatics, University of Bonn, Germany

Abstract

We study discrete k-clustering problems in general metric spaces that are constrained by a combination of two different fairness conditions within the demographic fairness model. Given a metric space (P,d), where every point in P is equipped with a protected attribute, and a number k, the goal is to partition P into k clusters with a designated center each, such that a center-based objective function is minimized and the attributes are fairly distributed with respect to the following two fairness concepts: 1) group fairness: We aim for clusters with balanced numbers of attributes by specifying lower and upper bounds for the desired attribute proportions. 2) diverse center selection: Clusters have natural representatives, i.e., their centers. We ask for a balanced set of representatives by specifying the desired number of centers to choose from each attribute. Dickerson, Esmaeili, Morgenstern and Zhang (2023) denote the combination of these two constraints as doubly constrained fair clustering. They present algorithms whose guarantees depend on the best known approximation factors for either of these problems. Currently, this implies an 8-approximation with a small additive violation on the group fairness constraint. For k-center, we improve this approximation factor to 4 with a small additive violation. This guarantee also depends on the currently best algorithm for DS-fair k-center given by Jones, Nguyen and Nguyen (2020). For k-median and k-means, we propose the first constant-factor approximation algorithms. Our algorithms transform a solution that satisfies diverse center selection into a doubly constrained fair clustering using an LP-based approach. Furthermore, our results are generalizable to other center-selection constraints, such as matroid k-clustering and knapsack constraints.

Explore similar work

CardsList
Sep 7, 2026cs.CG

A Sub-4 Approximation for Fair k-Means

Fairness in clustering has attracted sustained research interest, motivated by the need to ensure equitable representation of protected groups in machine learning applications. We study fair kk-means clustering in Euclidean space, where the proportion of each protected group in every cluster must lie within specified lower and upper bounds. These constraints make it challenging to determine both cluster centers and point assignments. We propose an approximation algorithm that combines a linear programming relaxation with geometric transformations of the input to construct candidate center sets. Given a ρρ-approximate algorithm for weighted kk-means and any ε>0ε>0, our algorithm returns a fractional solution whose cost is at most 1+(3−1/Γ)ρ+O(ε)1+(3-1/Γ)ρ+O(ε) times the optimal integral fair cost, where Γ≈6.357Γ\approx6.357 is an upper bound on the integrality gap of the standard Euclidean kk-means LP. With a PTAS as the subroutine, the approximation ratio becomes 3.8427+O(ε)3.8427+O(ε), improving the previous factor of 5+O(ε)5+O(ε) to below 44. The solution satisfies all fairness constraints exactly and can be rounded to an integral assignment with a bounded additive violation of fairness and no increase in cost. The same approximation guarantee extends to the kk-sparse Wasserstein barycenter problem.
Kangke Cheng, Guanlin Mo, Shihong Song +1
K$-MeansApproximation AlgorithmsFairness-Aware LearningOptimal Comparison AllocationClusterWasserstein Distance+1
AskPDF
Apr 27, 2023cs.LG

Proportionally Representative Clustering

In recent years, there has been a surge in effort to formalize notions of fairness in machine learning. We focus on centroid clustering--one of the fundamental tasks in unsupervised machine learning. We propose a new axiom ``proportionally representative fairness'' (PRF) that is designed for clustering problems where the selection of centroids reflects the distribution of data points and how tightly they are clustered together. Our fairness concept is not satisfied by existing fair clustering algorithms. We design efficient algorithms to achieve PRF both for unconstrained and discrete clustering problems. Our algorithm for the unconstrained setting is also the first known polynomial-time approximation algorithm for the well-studied Proportional Fairness (PF) axiom. Our algorithm for the discrete setting also matches the best known approximation factor for PF.
Haris Aziz, Barton E. Lee, Sean Morota Chu +1
ClusteringFairnessApproximation AlgorithmsOptimal Comparison AllocationMaximum Mean DiscrepancyUnsupervised+1
AskPDF
Jul 15, 2024cs.DS

Faster and Simpler Greedy Algorithm for k-Median and k-Means

Clustering problems such as kk-means and kk-median are staples of unsupervised learning, and many algorithmic techniques have been developed to tackle their numerous aspects. In this paper, we focus on the class of greedy approximation algorithm, that attracted less attention than local-search or primal-dual counterparts. In particular, we study the recursive greedy algorithm developed by Mettu and Plaxton [SIAM J. Comp 2003]. We provide a simplification of the algorithm, allowing for faster implementation, in graph metrics or in Euclidean space, where our algorithm matches or improves the state-of-the-art.
Max Dupré la Tour, David Saulpic
K$-MeansApproximation AlgorithmsClusteringMaximum Mean DiscrepancyUnsupervised
AskPDF