Saved in:
| Main Authors: | , , , , , |
|---|---|
| Format: | Preprint |
| Published: |
2025
|
| Subjects: | |
| Online Access: | https://arxiv.org/abs/2512.19654 |
| Tags: |
Add Tag
No Tags, Be the first to tag this record!
|
| _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 |