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$-中心的高效逼近算法。我们还构建了竞争性基准算法，并在各种真实数据集上对我们的逼近算法进行了实证评估。结果验证了我们的理论发现，并展示了我们的算法在聚类成本、聚类质量和运行时间方面的巨大优势。

具有背景知识的高效$k$-中心聚类