mlsanityData to 14 Oct 2026

Individual Preference Stability for Clustering

arXiv 2207.03600 ↗First posted 7 Jul 2022cs.LGcited by 8

Not on the map. Why?

Abstract (arXiv)

In this paper, we propose a natural notion of individual preference (IP) stability for clustering, which asks that every data point, on average, is closer to the points in its own cluster than to the points in any other cluster. Our notion can be motivated from several perspectives, including game theory and algorithmic fairness. We study several questions related to our proposed notion. We first show that deciding whether a given data set allows for an IP-stable clustering in general is NP-hard. As a result, we explore the design of efficient algorithms for finding IP-stable clusterings in some restricted metric spaces. We present a polytime algorithm to find a clustering satisfying exact IP-stability on the real line, and an efficient algorithm to find an IP-stable 2-clustering for a tree metric. We also consider relaxing the stability constraint, i.e., every data point should not be too far from its own cluster compared to any other cluster. For this case, we provide polytime algorithms with different guarantees. We evaluate some of our algorithms and several standard clustering approaches on real data sets.

Key facts. Cited by 8 papers in the map (data through 14 Oct 2026). Builds on 30 of its 69 references that are in the map. First posted on arXiv 7 Jul 2022.

Builds on

30 of 69 references.

References · 30

  1. 2014Certifying and removing disparate impactcited by 715
  2. 2018Fair Clustering Through Fairletscited by 176
  3. 2016Fairness in Learning: Classic and Contextual Banditscited by 168
  4. 2019Scalable Fair Clusteringcited by 78
  5. 2019Guarantees for Spectral Clustering with Fairness Constraintscited by 72
  6. 2019Proportionally Fair Clusteringcited by 69
  7. 2019Fair k-Center Clustering for Data Summarizationcited by 65
  8. 2018Online Learning with an Unknown Fairness Metriccited by 62
  9. 2020Individual Fairness for k-Clusteringcited by 56
  10. 2019Metric Learning for Individual Fairnesscited by 52
  11. 2019Coresets for Clustering with Fairness Constraintscited by 51
  12. 2019Clustering without Over-Representationcited by 50
18 more
  1. 2018On the cost of essentially fair clusteringscited by 44
  2. 2020Fair clustering via equitable group representationscited by 43
  3. 2021Improved Approximation Algorithms for Individually Fair Clusteringcited by 33
  4. 2020Probabilistic Fair Clusteringcited by 28
  5. 2021Better Algorithms for Individually Fair k-Clusteringcited by 28
  6. 2020Fair Correlation Clusteringcited by 27
  7. 2019A Center in Your Neighborhood: Fairness in Facility Locationcited by 26
  8. 2020A Pairwise Fair and Community-preserving Approach to k-Center Clusteringcited by 26
  9. 2020Fair Hierarchical Clusteringcited by 25
  10. 2021Approximation Algorithms for Socially Fair Clusteringcited by 25
  11. 2021Fairness, Semi-Supervised Learning, and More: A General Framework for Clustering with Stochastic Pairwise Constraintscited by 17
  12. 2020Distributional Individual Fairness in Clusteringcited by 14
  13. 2021Approximating Fair Clustering with Cascaded Norm Objectivescited by 13
  14. 2020KFC: A Scalable Approximation Algorithm for k-center Fair Clusteringcited by 12
  15. 2018Envy-Free Classificationcited by 11
  16. 2016Metric Perturbation Resiliencecited by 2
  17. 2019Principal Fairness: Removing Bias via Projectionscited by 1
  18. 2020Tree Embeddings for Hop-Constrained Network Designcited by 1

Built on by

Cited by year

Citing papers per year: 2023: 4; 2024: 4.

8 papers.

  1. 2023Proportional Fairness in Clustering: A Social Choice Perspectivecited by 13
  2. 2023Approximation Algorithms for Fair Range Clusteringcited by 10
  3. 2023Doubly Constrained Fair Clusteringcited by 9
  4. 2024Proportional Fairness in Non-Centroid Clusteringcited by 6
  5. 2023Constant Approximation for Individual Preference Stable Clusteringcited by 3
  6. 2024Optimization of Inter-group Criteria for Clustering with Minimum Size Constraintscited by 2
  7. 2024Scalable Algorithms for Individual Preference Stable Clusteringcited by 1
  8. 2024A Polynomial-Time Approximation for Pairwise Fair k-Median Clusteringcited by 0