# Clustering with Label Consistency

arXiv: https://arxiv.org/abs/2512.19654 · HTML: https://mlsanity.com/paper/2512.19654/

## 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 (most cited first, 14 of 14)

- [An Improved Approximation for k-median, and Positive Correlation in Budgeted Optimization](https://mlsanity.com/paper/1406.2951/) (2014)
- [Fully-Dynamic Coresets](https://mlsanity.com/paper/2004.14891/) (2020)
- [Sliding Window Algorithms for k-Clustering Problems](https://mlsanity.com/paper/2006.05850/) (2020)
- [Consistent k-Median: Simpler, Better and Robust](https://mlsanity.com/paper/2008.06101/) (2020)
- [Consistent k-Clustering for General Metrics](https://mlsanity.com/paper/2011.06888/) (2020)
- [Optimal Fully Dynamic k-Center Clustering for Adaptive and Oblivious Adversaries](https://mlsanity.com/paper/2303.11843/) (2023)
- [Improved Sliding Window Algorithms for Clustering and Coverage via Bucketing-Based Sketches](https://mlsanity.com/paper/2110.15533/) (2021)
- [Fully Dynamic Consistent k-Center Clustering](https://mlsanity.com/paper/2307.13747/) (2023)
- [Near-Optimal k-Clustering in the Sliding Window Model](https://mlsanity.com/paper/2311.00642/) (2023)
- [Efficient and Stable Fully Dynamic Facility Location](https://mlsanity.com/paper/2210.13880/) (2022)
- [Fully Dynamic k-Clustering with Fast Update Time and Small Recourse](https://mlsanity.com/paper/2408.01325/) (2024)
- [Fully Dynamic k-Median with Near-Optimal Update Time and Recourse](https://mlsanity.com/paper/2411.03121/) (2024)
- [Dynamic Consistent k-Center Clustering with Optimal Recourse](https://mlsanity.com/paper/2412.03238/) (2024)
- [Label-consistent clustering for evolving data](https://mlsanity.com/paper/2512.15210/) (2025)

## 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.