Clustering with Label Consistency

2025/12/22 by Diptarka Chakraborty, Chakraborty, Diptarka, Hendrik Fichtenberger +9
Business, Management and Accounting · Computer Science · #Advanced Clustering Algorithms Research #Artificial Intelligence (cs.AI) #Computational Geometry and Mesh Generation #Data Structures and Algorithms (cs.DS) #FOS: Computer and information sciences #Facility Location and Emergency Management

paper · doi:10.48550/arxiv.2512.19654

openalex publication_date 2025/12/22 · openalex created_date 2025/12/24 · openalex updated_date 2026/07/28

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.

Citations

• Label-consistent clustering for evolving data
• Dynamic Consistent k-Center Clustering with Optimal Recourse
• Fully Dynamic k-Median with Near-Optimal Update Time and Recourse
• Fully Dynamic k-Clustering with Fast Update Time and Small Recourse
• Near-Optimal k-Clustering in the Sliding Window Model
• Fully Dynamic Consistent k-Center Clustering
• Efficient and Stable Fully Dynamic Facility Location
• Improved Sliding Window Algorithms for Clustering and Coverage via Bucketing-Based Sketches
• Consistent k-Clustering for General Metrics
• Consistent k-Median: Simpler, Better and Robust
• Fully-Dynamic Coresets
• Approximation algorithms for metric facility location and k -Median problems using the primal-dual schema and Lagrangian relaxation
• A unified approach to approximation algorithms for bottleneck problems

Related

• Label-consistent clustering for evolving data
• Consistent k-Clustering for General Metrics
• Competitively Consistent Clustering
• Fully Dynamic k-Median with Near-Optimal Update Time and Recourse
• Accurate MapReduce Algorithms for k-median and k-means in General Metric Spaces