Clustering with Label Consistency
Fuente:
arXiv
Guardado en:
| Autores principales: | , , , , , |
|---|---|
| Formato: | Preprint |
| Publicado: |
2025
|
| Materias: | |
| Acceso en línea: | |
| Etiquetas: |
Agregar Etiqueta
Sin Etiquetas, Sea el primero en etiquetar este registro!
|
| _version_ | 1866911332978130944 |
|---|---|
| author | Chakraborty, Diptarka Fichtenberger, Hendrik Haeupler, Bernhard Lattanzi, Silvio Norouzi-Fard, Ashkan Svensson, Ola |
| author_facet | Chakraborty, Diptarka Fichtenberger, Hendrik Haeupler, Bernhard Lattanzi, Silvio Norouzi-Fard, Ashkan Svensson, Ola |
| contents | Designing efficient, effective, and consistent metric clustering algorithms is a significant challenge attracting growing attention. Traditional approaches focus on the stability of cluster centers; unfortunately, this neglects the real-world need for stable point labels, i.e., stable assignments of points to named sets (clusters). In this paper, we address this gap by initiating the study of label-consistent metric clustering. We first introduce a new notion of consistency, measuring the label distance between two consecutive solutions. Then, armed with this new definition, we design new consistent approximation algorithms for the classical $k$-center and $k$-median problems. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2512_19654 |
| institution | arXiv |
| publishDate | 2025 |
| record_format | arxiv |
| spellingShingle | Clustering with Label Consistency Chakraborty, Diptarka Fichtenberger, Hendrik Haeupler, Bernhard Lattanzi, Silvio Norouzi-Fard, Ashkan Svensson, Ola Data Structures and Algorithms Artificial Intelligence Designing efficient, effective, and consistent metric clustering algorithms is a significant challenge attracting growing attention. Traditional approaches focus on the stability of cluster centers; unfortunately, this neglects the real-world need for stable point labels, i.e., stable assignments of points to named sets (clusters). In this paper, we address this gap by initiating the study of label-consistent metric clustering. We first introduce a new notion of consistency, measuring the label distance between two consecutive solutions. Then, armed with this new definition, we design new consistent approximation algorithms for the classical $k$-center and $k$-median problems. |
| title | Clustering with Label Consistency |
| topic | Data Structures and Algorithms Artificial Intelligence |
| url | https://arxiv.org/abs/2512.19654 |