Scalable Algorithms for Individual Preference Stable Clustering
Not on the map. Why?
Abstract (arXiv)
In this paper, we study the individual preference (IP) stability, which is an notion capturing individual fairness and stability in clustering. Within this setting, a clustering is α-IP stable when each data point's average distance to its cluster is no more than α times its average distance to any other cluster. In this paper, we study the natural local search algorithm for IP stable clustering. Our analysis confirms a O(log n)-IP stability guarantee for this algorithm, where n denotes the number of points in the input. Furthermore, by refining the local search approach, we show it runs in an almost linear time, tildeO(nk).
Key facts. Cited by 1 paper in the map (data through 7 Oct 2026). Builds on 30 of its 57 references that are in the map. First posted on arXiv 15 Mar 2024.
Builds on
30 of 57 references.
References · 30
- 2018Fair Clustering Through Fairletscited by 176
- 2019Fair Algorithms for Clusteringcited by 98
- 2019Scalable Fair Clusteringcited by 78
- 2019Fair k-Center Clustering for Data Summarizationcited by 65
- 2017From Parity to Preference-based Notions of Fairness in Classificationcited by 60
- 2020Individual Fairness for k-Clusteringcited by 56
- 2019Clustering without Over-Representationcited by 50
- 2018On the cost of essentially fair clusteringscited by 44
- 2020Fair clustering via equitable group representationscited by 43
- 2021Improved Approximation Algorithms for Individually Fair Clusteringcited by 33
- 2021Better Algorithms for Individually Fair k-Clusteringcited by 28
- 2019A Center in Your Neighborhood: Fairness in Facility Locationcited by 26
18 more
- 2020A Pairwise Fair and Community-preserving Approach to k-Center Clusteringcited by 26
- 2017Constant Approximation for k-Median and k-Means with Outliers via Iterative Roundingcited by 25
- 2021Approximation Algorithms for Socially Fair Clusteringcited by 25
- 2021A New Notion of Individually Fair Clustering: α-Equitable k-Centercited by 18
- 2021Fairness, Semi-Supervised Learning, and More: A General Framework for Clustering with Stochastic Pairwise Constraintscited by 17
- 2020Distributional Individual Fairness in Clusteringcited by 14
- 2021Approximating Fair Clustering with Cascaded Norm Objectivescited by 13
- 2020How to Solve Fair k-Center in Massive Data Modelscited by 12
- 2013Matroid and Knapsack Center Problemscited by 11
- 2018Envy-Free Classificationcited by 11
- 2023Approximation Algorithms for Fair Range Clusteringcited by 10
- 2022Constant-Factor Approximation Algorithms for Socially Fair k-Clusteringcited by 8
- 2022Individual Preference Stability for Clusteringcited by 8
- 2021Feature-based Individual Fairness in k-Clusteringcited by 4
- 2022Fair Representation Clustering with Several Protected Classescited by 4
- 2023Constant Approximation for Individual Preference Stable Clusteringcited by 3
- 2016Metric Perturbation Resiliencecited by 2
- 2024Optimization of Inter-group Criteria for Clustering with Minimum Size Constraintscited by 2
Built on by
Citing papers per year: 2024: 1.
1 paper.