  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.
