{"ID":2826378,"CreatedAt":"2026-06-01T04:54:23.091178241Z","UpdatedAt":"2026-06-01T04:54:23.091178241Z","DeletedAt":null,"paper_url":"https://arxiv.org/abs/2512.19654","arxiv_id":"2512.19654","title":"Clustering with Label Consistency","abstract":"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.","short_abstract":"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 set...","url_abs":"https://arxiv.org/abs/2512.19654","url_pdf":"https://arxiv.org/pdf/2512.19654v1","authors":"[\"Diptarka Chakraborty\",\"Hendrik Fichtenberger\",\"Bernhard Haeupler\",\"Silvio Lattanzi\",\"Ashkan Norouzi-Fard\",\"Ola Svensson\"]","published":"2025-12-22T18:32:23Z","proceeding":"cs.DS","tasks":"[\"cs.DS\",\"cs.AI\"]","methods":"[]","has_code":false}