Scalable Algorithms for Individual Preference Stable Clustering

Ron Mosenzon, Ali Vakilian
3/15/2024
cs.DScs.AIcs.CY

No confident code implementation found for this paper.

Abstract

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, $\tilde{O}(nk)$.

View on arXivView PDF

Code Implementations

No confident code match yet

We couldn't find an author-owned or strongly-evidenced community implementation for this paper. Any repos shown below are weak matches — verify before relying on them.

No code implementations found yet.

Know of an implementation? Let us know in the comments below!

Similar Papers

Constant Approximation for Individual Preference Stable Clustering

95% match2026

Neighborhood Stability as a Measure of Nearest Neighbor Searchability

81% match2026

The Computational Complexity of Almost Stable Clustering with Penalties

78% match2025

A High-Performance External Validity Index for Clustering with a Large Number of Clusters

78% match2024

Robust Markov stability for community detection at a scale learned based on the structure

77% match1 repo12025

Interpretable label-free self-guided subspace clustering

77% match2024

Cite this paper

@article{mosenzon2024scalable,
  title  = {Scalable Algorithms for Individual Preference Stable Clustering},
  author = {Ron Mosenzon and Ali Vakilian},
  year   = {2024},
  eprint = {2403.10365},
  archivePrefix = {arXiv},
  url    = {http://arxiv.org/abs/2403.10365v1}
}

Add a badge to your README

Shows whether official code is linked for this paper.

Code of Paper badge
[![Code of Paper](https://codeofpaper.com/badge/2403.10365.svg)](https://codeofpaper.com/paper/2403.10365)

Discussion