Approximating k-center problem using Hierarchical Clustering

Abstract

The K-center problem is a classical problem in facility location: given n cities and the distances between them, we wish to select k of these cities as centers so that the maximum distance of a city from its closest center is minimized. The problem is NP-hard problem. For this thesis the vertices or node must be in a metric space. In this thesis agglomerative hierarchical clustering with complete linkage is used which divides the graph of nodes into set of clusters. For each node within the cluster the maximum distance to its center will be minimum. Finding cluster center is another task named as 1-center problem which states as the smallest circle that contains all of a given set of points i.e. the maximum radius circle to include all nodes will be minimum. In this thesis k-center problem is solved in metric space graph first by clustering nodes of graph and then finding k center within each cluster. Finally the result is compared with existing methods for k center problem and 1-center problem.