# Linear Programming based Approximation to Individually Fair k-Clustering with Outliers

arXiv: https://arxiv.org/abs/2412.10923 · HTML: https://mlsanity.com/paper/2412.10923/

## Key facts

- Cited by 1 papers in the map (data through 14 Oct 2026).
- Builds on 13 of its 28 references that are in the map.
- First posted on arXiv 14 Dec 2024.

## Builds on (most cited first, 13 of 13)

- [Fair Clustering Through Fairlets](https://mlsanity.com/paper/1802.05733/) (2018)
- [Fair Algorithms for Clustering](https://mlsanity.com/paper/1901.02393/) (2019)
- [Scalable Fair Clustering](https://mlsanity.com/paper/1902.03519/) (2019)
- [Proportionally Fair Clustering](https://mlsanity.com/paper/1905.03674/) (2019)
- [Individual Fairness for k-Clustering](https://mlsanity.com/paper/2002.06742/) (2020)
- [Coresets for Clustering with Fairness Constraints](https://mlsanity.com/paper/1906.08484/) (2019)
- [On the cost of essentially fair clusterings](https://mlsanity.com/paper/1811.10319/) (2018)
- [Improved Approximation Algorithms for Individually Fair Clustering](https://mlsanity.com/paper/2106.14043/) (2021)
- [Better Algorithms for Individually Fair k-Clustering](https://mlsanity.com/paper/2106.12150/) (2021)
- [A Center in Your Neighborhood: Fairness in Facility Location](https://mlsanity.com/paper/1908.09041/) (2019)
- [Constant Approximation for k-Median and k-Means with Outliers via Iterative Rounding](https://mlsanity.com/paper/1711.01323/) (2017)
- [A Scalable Algorithm for Individually Fair K-means Clustering](https://mlsanity.com/paper/2402.06730/) (2024)
- [Fast Noise Removal for k-Means Clustering](https://mlsanity.com/paper/2003.02433/) (2020)

## Built on by (most cited first, 1 of 1)

- [Individual Fairness in Hierarchical Clustering](https://mlsanity.com/paper/2608.25586/) (2026)

## Abstract (arXiv)

Individual fairness guarantees are often desirable properties to have, but they become hard to formalize when the dataset contains outliers. Here, we investigate the problem of developing an individually fair k-means clustering algorithm for datasets that contain outliers. That is, given n points and k centers, we want that for each point which is not an outlier, there must be a center within the fracnk nearest neighbours of the given point. While a few of the recent works have looked into individually fair clustering, this is the first work that explores this problem in the presence of outliers for k-means clustering. For this purpose, we define and solve a linear program (LP) that helps us identify the outliers. We exclude these outliers from the dataset and apply a rounding algorithm that computes the k centers, such that the fairness constraint of the remaining points is satisfied. We also provide theoretical guarantees that our method leads to a guaranteed approximation of the fair radius as well as the clustering cost. We also demonstrate our techniques empirically on real-world datasets.