Fair Clustering: Concepts, Methods, and Algorithms

Abstract

Clustering is a foundational task in machine learning and data analysis, yet its classical objectives — $k$-center, $k$-median, and $k$-means — optimize solely for proximity and may treat individuals from different demographic or social groups inequitably. This survey provides an algorithmic overview of fair clustering, with an emphasis on theoretical models, approximation guarantees, and the techniques that underlie them. We organize the discussion by how fairness is defined: group-fairness notions, including balanced representation within clusters, demographic constraints on the chosen centers, and minimizing the worst-case (socially fair) cost across groups; individual fairness, which asks that comparable points receive comparable service; and proportionality and stability notions drawn from cooperative game theory. Our focus throughout is on centroid-based objectives, and we summarize the recurring algorithmic ideas — fairlet decomposition, linear-programming relaxation and rounding, coresets, metric embeddings, and local search — together with representative results and open problems. This is intended as a curated rather than comprehensive account of the core algorithmic contributions that have shaped the area.

This survey is a living document and remains under active construction; sections may be revised, expanded, or added over time.