Center-based clustering has attracted significant research interest from both
theory and practice. In many practical applications, input data often contain
background knowledge that can be used to improve clustering results. In this
work, we build on widely adopted $k$-center clustering and model its input
background knowledge as must-link (ML) and cannot-link (CL) constraint sets.
However, most clustering problems including $k$-center are inherently
$\mathcal{NP}$-hard, while the more complex constrained variants are known to
suffer severer approximation and computation barriers that significantly limit
their applicability. By employing a suite of techniques including reverse
dominating sets, linear programming (LP) integral polyhedron, and LP duality,
we arrive at the first efficient approximation algorithm for constrained
$k$-center with the best possible ratio of 2. We also construct competitive
baseline algorithms and empirically evaluate our approximation algorithm
against them on a variety of real datasets. The results validate our
theoretical findings and demonstrate the great advantages of our algorithm in
terms of clustering cost, clustering quality, and running time.

在这项工作中，我们在广泛采用的 $k$- 中心聚类的基础上构建其输入的背景知识作为必连（ML）和禁连（CL）约束集，并通过使用一系列技术，包括反支配集、线性规划整体多面体和线性规划对偶，得出了第一个具有最佳比例 2 的约束 $k$- 中心的高效逼近算法。我们还构建了竞争性基准算法，并在各种真实数据集上对我们的逼近算法进行了实证评估。结果验证了我们的理论发现，并展示了我们的算法在聚类成本、聚类质量和运行时间方面的巨大优势。