# Approximation Algorithm for Constrained k-Center Clustering: A Local Search Approach

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

## Key facts

- Cited by 1 papers in the map (data through 14 Oct 2026).
- Builds on 5 of its 26 references that are in the map.
- First posted on arXiv 17 Jan 2026.

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

- [Fairness, Semi-Supervised Learning, and More: A General Framework for Clustering with Stochastic Pairwise Constraints](https://mlsanity.com/paper/2103.02013/) (2021)
- [An Improved Local Search Algorithm for k-Median](https://mlsanity.com/paper/2111.04589/) (2021)
- [K-means for Evolving Data Streams](https://mlsanity.com/paper/2012.03628/) (2020)
- [Near-Optimal Algorithms for Constrained k-Center Clustering with Instance-level Background Knowledge](https://mlsanity.com/paper/2401.12533/) (2024)
- [Scalable Facility Location for Massive Graphs on Pregel-like Systems](https://mlsanity.com/paper/1503.03635/) (2015)

## Built on by (most cited first, 1 of 1)

- [Parameterized and Streaming Algorithms for Euclidean Fair k-Center Clustering](https://mlsanity.com/paper/2609.06384/) (2026)

## Abstract (arXiv)

Clustering is a long-standing research problem and a fundamental tool in AI and data analysis. The traditional k-center problem, a fundamental theoretical challenge in clustering, has a best possible approximation ratio of 2, and any improvement to a ratio of 2 - ε would imply P = NP. In this work, we study the constrained k-center clustering problem, where instance-level cannot-link (CL) and must-link (ML) constraints are incorporated as background knowledge. Although general CL constraints significantly increase the hardness of approximation, previous work has shown that disjoint CL sets permit constant-factor approximations. However, whether local search can achieve such a guarantee in this setting remains an open question. To this end, we propose a novel local search framework based on a transformation to a dominating matching set problem, achieving the best possible approximation ratio of 2. The experimental results on both real-world and synthetic datasets demonstrate that our algorithm outperforms baselines in solution quality.