# Kempe Swap K-Means: A Scalable Near-Optimal Solution for Semi-Supervised Clustering

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

## Key facts

- No citing papers in the map yet (data through 14 Oct 2026).
- Builds on 3 of its 21 references that are in the map.
- First posted on arXiv 28 Mar 2026.

## Builds on (most cited first, 3 of 3)

- [An Exact Algorithm for Semi-supervised Minimum Sum-of-Squares Clustering](https://mlsanity.com/paper/2111.15571/) (2021)
- [An algorithm for clustering with confidence-based must-link and cannot-link constraints](https://mlsanity.com/paper/2212.14437/) (2022)
- [A Binary Optimization Approach for Constrained K-Means Clustering](https://mlsanity.com/paper/1810.10134/) (2018)

## Abstract (arXiv)

This paper presents a novel centroid-based heuristic algorithm, termed Kempe Swap K-Means, for constrained clustering under rigid must-link (ML) and cannot-link (CL) constraints. The algorithm employs a dual-phase iterative process: an assignment step that utilizes Kempe chain swaps to refine current clustering in the constrained solution space and a centroid update step that computes optimal cluster centroids. To enhance global search capabilities and avoid local optima, the framework incorporates controlled perturbations during the update phase. Empirical evaluations demonstrate that the proposed method achieves near-optimal partitions while maintaining high computational efficiency and scalability. The results indicate that Kempe Swap K-Means consistently outperforms state-of-the-art benchmarks in both clustering accuracy and algorithmic efficiency for large-scale datasets.