Near-Optimal Algorithms for Constrained k-Center Clustering with Instance-level Background Knowledge
This provides a near-optimal solution for clustering with instance-level constraints, addressing a bottleneck in practical applications where background knowledge is available.
The paper tackles the NP-hard constrained k-center clustering problem with must-link and cannot-link constraints, achieving the first efficient approximation algorithm with an optimal ratio of 2 and demonstrating advantages in cost, quality, and runtime on real datasets.
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.