Exact k-Center Clustering on Graphs for Small k

Abstract

k-center clustering on graphs is widely used in data mining tasks such as prototype selection, facility placement, and dataset summarization. Despite its importance, practitioners rely almost entirely on approximation algorithms or heuristics due to the perceived impracticality of exact computation. We show that exact k-center becomes tractable and scalable in the small-k regime introducing a new exact algorithm that borrows concepts from LP-type optimization to obtain exact solutions for interesting classes of real-world datasets. We provide theoretical justification and extensive experiments demonstrating the practicability of our approach. Our findings challenge the conventional assumption that exact k-center is impractical and establish a new practical regime for optimal clustering.