Scalable Algorithms for Individual Preference Stable Clustering
Fuente:
arXiv
Saved in:
| Main Authors: | , |
|---|---|
| Format: | Preprint |
| Published: |
2024
|
| Subjects: | |
| Online Access: | |
| Tags: |
Add Tag
No Tags, Be the first to tag this record!
|
| _version_ | 1866916160400785408 |
|---|---|
| author | Mosenzon, Ron Vakilian, Ali |
| author_facet | Mosenzon, Ron Vakilian, Ali |
| contents | 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)$. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2403_10365 |
| institution | arXiv |
| publishDate | 2024 |
| record_format | arxiv |
| spellingShingle | Scalable Algorithms for Individual Preference Stable Clustering Mosenzon, Ron Vakilian, Ali Data Structures and Algorithms Artificial Intelligence Computers and Society Machine Learning 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)$. |
| title | Scalable Algorithms for Individual Preference Stable Clustering |
| topic | Data Structures and Algorithms Artificial Intelligence Computers and Society Machine Learning |
| url | https://arxiv.org/abs/2403.10365 |