Skip to content

A Sub-4 Approximation for Fair $k$-Means

Sep 2026 · 0 citations · 48 references
Computer Science

TL;DR

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.

View source

Similar papers

Sep 2026

Rounding the Ball LP for Fair Max-Min Diversification

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 · 0 citations
Preprint Sep 2026

Local Search for Fair Max-Min Diversification

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
#machine learning Preprint Oct 2026

Streaming algorithms for robust max-min diversification

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
Preprint Sep 2026

A New Perspective on Clustering: A Mixed-norm Model and its Solution by Progressive Integer Programming

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
#artificial intelligence Conference Open access Sep 2026

Parameterized and Streaming Algorithms for Euclidean Fair k-Center Clustering

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. · 0 citations
Preprint Sep 2026

A PTAS for Non-Adaptive Stochastic Top-$k$ Sum under General Combinatorial Constraints

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 Nov 17, 2026

Learning the language of machine learning

By studying the computational foundations of language learning, Associate Professor Jacob Andreas builds intelligent systems that can communicate effectively with humans.

Microsoft Research Blog Nov 16, 2026

TokenEconomizer: Learning from Experience to Make AI Coding Agents More Efficient

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.

We use cookies to run the site and, with your consent, for analytics and to show ads. See our Cookie Policy.