mlsanityData to 14 Oct 2026

Better Algorithms for Individually Fair k-Clustering

arXiv 2106.12150 ↗First posted 23 Jun 2021cs.DS cs.CY cs.LGcited by 28

Not on the map. Why?

Abstract (arXiv)

We study data clustering problems with ℓp-norm objectives (e.g. k-Median and k-Means) in the context of individual fairness. The dataset consists of n points, and we want to find k centers such that (a) the objective is minimized, while (b) respecting the individual fairness constraint that every point v has a center within a distance at most r(v), where r(v) is v's distance to its (n/k)th nearest point. Jung, Kannan, and Lutz [FORC 2020] introduced this concept and designed a clustering algorithm with provable (approximate) fairness and objective guarantees for the ℓ_∞ or k-Center objective. Mahabadi and Vakilian [ICML 2020] revisited this problem to give a local-search algorithm for all ℓp-norms. Empirically, their algorithms outperform Jung et. al.'s by a large margin in terms of cost (for k-Median and k-Means), but they incur a reasonable loss in fairness. In this paper, our main contribution is to use Linear Programming (LP) techniques to obtain better algorithms for this problem, both in theory and in practice. We prove that by modifying known LP rounding techniques, one gets a worst-case guarantee on the objective which is much better than in MV20, and empirically, this objective is extremely close to the optimal. Furthermore, our theoretical fairness guarantees are comparable with MV20 in theory, and empirically, we obtain noticeably fairer solutions. Although solving the LP em exactly might be prohibitive, we demonstrate that in practice, a simple sparsification technique drastically improves the run-time of our algorithm.

Key facts. Cited by 28 papers in the map (data through 14 Oct 2026). Builds on 16 of its 37 references that are in the map. First posted on arXiv 23 Jun 2021.

Builds on

16 of 37 references.

References · 16

  1. 2018Fair Clustering Through Fairletscited by 176
  2. 2016Fairness in Learning: Classic and Contextual Banditscited by 168
  3. 2019Fair Algorithms for Clusteringcited by 98
  4. 2016Measuring Fairness in Ranked Outputscited by 81
  5. 2017Ranking with Fairness Constraintscited by 78
  6. 2019Proportionally Fair Clusteringcited by 69
  7. 2020Individual Fairness for k-Clusteringcited by 56
  8. 2016Better Guarantees for k-Means and Euclidean k-Median by Primal-Dual Algorithmscited by 54
  9. 2020Fair clustering via equitable group representationscited by 43
  10. 2014An Improved Approximation for k-median, and Positive Correlation in Budgeted Optimizationcited by 26
  11. 2020On Approximability of Clustering Problems Without Candidate Centerscited by 13
  12. 2018Approximation Algorithms for Minimum Norm and Ordered Optimization Problemscited by 11
4 more
  1. 2017Constant-Factor Approximation for Ordered k-Mediancited by 8
  2. 2018Approximation algorithms for stochastic clusteringcited by 7
  3. 2017Interpolating between k-Median and k-Center: Approximation Algorithms for Ordered k-Mediancited by 6
  4. 2021Revisiting Priority k-Center: Fairness and Outlierscited by 4

Built on by

Cited by year

Citing papers per year: 2021: 5; 2022: 4; 2023: 10; 2024: 7; 2025: 2.

28 papers.

Sort:

  1. 2021Improved Approximation Algorithms for Individually Fair Clusteringcited by 33
  2. 2021Near-Optimal Explainable k-Means for All Dimensionscited by 13
  3. 2023Proportional Fairness in Clustering: A Social Choice Perspectivecited by 13
  4. 2023Approximation Algorithms for Fair Range Clusteringcited by 10
  5. 2022Individual Preference Stability for Clusteringcited by 8
  6. 2023Learning Informative Representation for Fairness-aware Multivariate Time-series Forecasting: A Group-based Perspectivecited by 8
  7. 2023Proportionally Representative Clusteringcited by 8
  8. 2023Fair Wasserstein Coresetscited by 8
  9. 2024A Scalable Algorithm for Individually Fair K-means Clusteringcited by 8
  10. 2021Efficient Algorithms For Fair Clustering with a New Fairness Notioncited by 5
  11. 2021Feature-based Individual Fairness in k-Clusteringcited by 4
  12. 2022Fair Representation Clustering with Several Protected Classescited by 4
16 more
  1. 2021Modification-Fair Cluster Editingcited by 3
  2. 2023Spectral Normalized-Cut Graph Partitioning with Fairness Constraintscited by 3
  3. 2023Constant Approximation for Individual Preference Stable Clusteringcited by 3
  4. 2024On Socially Fair Low-Rank Approximation and Column Subset Selectioncited by 2
  5. 2022Measuring and mitigating voting access disparities: a study of race and polling locations in Florida and North Carolinacited by 1
  6. 2023Fair Clustering via Hierarchical Fair-Dirichlet Processcited by 1
  7. 2023Dual Node and Edge Fairness-Aware Graph Partitioncited by 1
  8. 2023Fair Clustering: A Causal Perspectivecited by 1
  9. 2024Scalable Algorithms for Individual Preference Stable Clusteringcited by 1
  10. 2024The Fairness-Quality Trade-off in Clusteringcited by 1
  11. 2024Linear Programming based Approximation to Individually Fair k-Clustering with Outlierscited by 1
  12. 2025Adversarial Fair Multi-View Clusteringcited by 1
  13. 2022Bicriteria Approximation Algorithms for Priority Matroid Mediancited by 0
  14. 2024A Polynomial-Time Approximation for Pairwise Fair k-Median Clusteringcited by 0
  15. 2024Efficient k-means with Individual Fairness via Exponential Tiltingcited by 0
  16. 2025Autonomy-Aware Clustering: When Local Decisions Supersede Global Prescriptionscited by 0