arXiv preprint ·
A Sub-4 Approximation for Fair $k$-Means
- Published
- Source
- arXiv preprint, posted before peer review
- Original
- Read it at arXiv
- Topics
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 $ρ$-approximate algorithm for weighted $k$-means and any $ε>0$, our algorithm returns a fractional solution whose cost is at most $1+(3-1/Γ)ρ+O(ε)$ times the optimal integral fair cost, where $Γ\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(ε)$, improving the previous factor of $5+O(ε)$ 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.
The authors’ abstract, as arXiv lists it. arXiv’s listings, abstracts included, are free for anyone to reuse.
Read it on ReadSearch
Each opens after you create an account, and brings you back to this paper.
More in Computational Geometry
Learn the Solid, Not the File: Canonical Inputs for Neural Networks on CAD Boundary Representations
Direct Topology Tracking in Continuous Implicit Models
Low-Dimensional Embeddings for Gaussian Kernels on Manifolds
Perfectly Guarding Straits: Exact Algorithms for Weak Visibility Polygons
Multi-Stage NeRF for Efficient 3D Coronary Artery Reconstruction from Two Narrow-Angle Angiographic Projections
Get the few papers worth your time in Computational Geometry every morning.
ReadSearch reads the new papers in your field each day and brings you the few worth reading, each with its key finding in a sentence.