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

Clustering is a long-standing research problem and a fundamental tool in AI and data analysis. The traditional $k$-center problem, known as a fundamental theoretical challenge in clustering, has a best possible approximation ratio of $2$, and any improvement to a ratio of $2 - \epsilon$ would imply $\mathcal{P} = \mathcal{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 \textit{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 all baseline methods in solution quality.