Facility location on graphs

hek-center problem is that of choosing k vertices as centers in a weighted undirected graph in which the edge weights obey the triangle inequality so that the maximum distance of any vertex to its nearest center is minimized. The problem is NP-hard, but there is a simple greedy 2-approximation algorithm which has been shown to be optimal. We consider here the capacitated k-center problem, where additionally each vertex has a capacity, which is a bound on the number of ‘clients’ it can serve if it is opened as a center. Unlike the uncapacitated k-center problem, our understanding of the capacitated version is far from complete. We mainly concern ourselves with the case when all capacities are equal, which is called the uniform capacity k-center problem. We give here an L-approximation for the uniform k-center problem where each vertex has capacity L.