The balanced K-center problem is a fundamental facility location
problem, where we are asked to locate K facilities in a graph, and to assign
vertices to facilities, so as to minimize the maximum distance from a
vertex to the facility to which it is assigned. Moreover, each facility may be
assigned at most L vertices. This problem is known to be NP-hard. We give
polynomial time approximation algorithms for two different versions of this
problem that achieve approximation factors of 5 and 6.
(Joint work with Samir Khuller.)