Near-Optimal Algorithms for Constrained k-Center Clustering with Instance-level Background Knowledge

arXiv:2401.12533v2 Announce Type: replace
Abstract: 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 …

abstract algorithms applications arxiv build center clustering cs.ai cs.lg data instance knowledge near practical practice research results theory type work