Faster and Simpler Greedy Algorithm for $k$-Median and $k$-Means
Fuente:
arXiv
Enregistré dans:
| Auteurs principaux: | , |
|---|---|
| Format: | Preprint |
| Publié: |
2024
|
| Sujets: | |
| Accès en ligne: | |
| Tags: |
Ajouter un tag
Pas de tags, Soyez le premier à ajouter un tag!
|
| _version_ | 1866909874222268416 |
|---|---|
| author | la Tour, Max Dupré Saulpic, David |
| author_facet | la Tour, Max Dupré Saulpic, David |
| contents | Clustering problems such as $k$-means and $k$-median are staples of unsupervised learning, and many algorithmic techniques have been developed to tackle their numerous aspects.
In this paper, we focus on the class of greedy approximation algorithm, that attracted less attention than local-search or primal-dual counterparts. In particular, we study the recursive greedy algorithm developed by Mettu and Plaxton [SIAM J. Comp 2003]. We provide a simplification of the algorithm, allowing for faster implementation, in graph metrics or in Euclidean space, where our algorithm matches or improves the state-of-the-art. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2407_11217 |
| institution | arXiv |
| publishDate | 2024 |
| record_format | arxiv |
| spellingShingle | Faster and Simpler Greedy Algorithm for $k$-Median and $k$-Means la Tour, Max Dupré Saulpic, David Data Structures and Algorithms Artificial Intelligence Clustering problems such as $k$-means and $k$-median are staples of unsupervised learning, and many algorithmic techniques have been developed to tackle their numerous aspects. In this paper, we focus on the class of greedy approximation algorithm, that attracted less attention than local-search or primal-dual counterparts. In particular, we study the recursive greedy algorithm developed by Mettu and Plaxton [SIAM J. Comp 2003]. We provide a simplification of the algorithm, allowing for faster implementation, in graph metrics or in Euclidean space, where our algorithm matches or improves the state-of-the-art. |
| title | Faster and Simpler Greedy Algorithm for $k$-Median and $k$-Means |
| topic | Data Structures and Algorithms Artificial Intelligence |
| url | https://arxiv.org/abs/2407.11217 |