Clustering with Label Consistency
Not on the map. Why?
Abstract (arXiv)
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.
Key facts. No citing papers in the map yet (data through 14 Oct 2026). Builds on 14 of its 30 references that are in the map. First posted on arXiv 22 Dec 2025.
Builds on
14 of 30 references.
References · 14
- 2014An Improved Approximation for k-median, and Positive Correlation in Budgeted Optimizationcited by 26
- 2020Fully-Dynamic Coresetscited by 9
- 2020Sliding Window Algorithms for k-Clustering Problemscited by 7
- 2020Consistent k-Median: Simpler, Better and Robustcited by 7
- 2020Consistent k-Clustering for General Metricscited by 7
- 2023Optimal Fully Dynamic k-Center Clustering for Adaptive and Oblivious Adversariescited by 6
- 2021Improved Sliding Window Algorithms for Clustering and Coverage via Bucketing-Based Sketchescited by 5
- 2023Fully Dynamic Consistent k-Center Clusteringcited by 5
- 2023Near-Optimal k-Clustering in the Sliding Window Modelcited by 4
- 2022Efficient and Stable Fully Dynamic Facility Locationcited by 3
- 2024Fully Dynamic k-Clustering with Fast Update Time and Small Recoursecited by 3
- 2024Fully Dynamic k-Median with Near-Optimal Update Time and Recoursecited by 3
2 more
- 2024Dynamic Consistent k-Center Clustering with Optimal Recoursecited by 2
- 2025Label-consistent clustering for evolving datacited by 1
Built on by
Not cited yet.