This work proposes an approximation algorithm that combines a linear programming relaxation with geometric transformations of the input to construct candidate center sets in fair $k-means clustering in Euclidean space and satisfies all fairness constraints exactly.
Abstract
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 $k$-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 $\rho$-approximate algorithm for weighted $k$-means and any $\epsilon>0$, our algorithm returns a fractional solution whose cost is at most $1+(3-1/\Gamma)\rho+O(\epsilon)$ times the optimal integral fair cost, where $\Gamma\approx6.357$ is an upper bound on the integrality gap of the standard Euclidean $k$-means LP. With a PTAS as the subroutine, the approximation ratio becomes $3.8427+O(\epsilon)$, improving the previous factor of $5+O(\epsilon)$ to below $4$. 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 $k$-sparse Wasserstein barycenter problem.
Given $n$ points in a metric space, partitioned into groups, $X_1,\dots,X_m$, and integer quotas, $k_1,\dots,k_m$, summing to $k$, the Fair Max-Min Diversification problem asks for a set of $k$ points, exactly $k_i$ from each group $X_i$, maximizing the minimum pairwise distance. Addanki et al. (ICDT 2022) described a...
Julián Mestre, Lam Khai Trinh, Anthony Wirth· arXiv.org· 0 citations
Given $n$ points in a metric space, Max-Min diversification asks for a subset of $k$ points maximizing the minimum pairwise distance between the selected points. This is arguably the most fundamental notion of diversity with applications across a wide range of domains. We consider this problem under partition constrain...
S. Mahabadi, Shyam Narayanan, Varun Sivashankar· 0 citations
Given a set of $n$ points $X$ in a metric space and an integer $k$, max-min diversification aims to select $k$ points of $X$ maximizing their minimum pairwise distance. This objective function is however highly vulnerable to noisy points. In[Amagata, AAAI23], a robust formulation is proposed which addresses this vulner...
A. Pietracaprina, G. Pucci, Stefano Zanon· 0 citations
This paper introduces an $\ell_{p,q}$ mixed-norm clustering model where the centroid updates and cluster assignments are under the $\ell_p$ and $\ell_q$ norms, respectively, and develops a progressive integer programming method that adaptively fixes confident assignments and solves restricted mixed-integer subproblems.
Jun-Yi Liu, Yu-Lin Peng, Yao Xie et al.· 0 citations
This work develops a parameterized approximation algorithm for Euclidean fair k-center clustering with an approximation ratio of 4.732 and designs a one-pass streaming algorithm with an approximation ratio of 4.42, outperforming the state-of-the-art ratio.
Ze-Yu Lin, Chaoqi Jia, Long-Kun Guo et al.· Proceedings of the Thirty-Fi...· 0 citations
We study non-adaptive selection of a feasible set $S$ that maximizes the expected sum of the $k$ largest realized values among independent nonnegative discrete random variables. The same objective arises in team hiring and as VCG welfare in an $\ell$-unit auction. The main setting is a fixed-dimensional nonnegative pac...
Yu Liu· 0 citations
Related blog posts
MIT News · Artificial Intelligence· news.mit.eduNov 17, 2026
By studying the computational foundations of language learning, Associate Professor Jacob Andreas builds intelligent systems that can communicate effectively with humans.
Microsoft Research Blog· microsoft.comNov 16, 2026
AI coding agents are increasingly help developers fix bugs and build features largely on their own, but every interaction with their models consumes tokens. In each session, an agent sends instructions, tool descriptions, and session history to its model. Most efforts to reduce this cost focus on individual tasks. Yet developers return to the same […] The post TokenEconomizer: Learning from Experience to Make AI Coding Agents More Efficient appeared first on Microsoft Research.
MIT News · Artificial Intelligence· news.mit.eduNov 13, 2026