Efficient Constrained K-center Clustering with Background Knowledge

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 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.

Authors

• Longkun Guo College of Computer and Data Science, Fuzhou University Shandong Fundamental Research Center for Computer Science
• Chaoqi Jia Key Laboratory of Computing Power Network and Information Security, Ministry of Education, Shandong Computer Science Center, Qilu University of Technology (Shandong Academy of Sciences), Jinan 250316, China
• Kewen Liao HilstLab, Peter Faber Business School, Australian Catholic University, Sydney 2060, Australia
• Zhigang Lu College of Science and Engineering, James Cook University, Townsville 4810, Australia
• Minhui Xue CSIRO's Data61, Sydney 2015, Australia

Keywords

• ML: Clustering
• SO: Combinatorial Optimization