The Heterogeneous Capacitated k-Center Problem

Abstract

In this paper we initiate the study of the heterogeneous capacitated k -center problem: we are given a metric space X=(F∪C,d) , and a collection of capacities. The goal is to open each capacity at a unique facility location in F, and also to assign clients to facilities so that the number of clients assigned to any facility is at most the capacity installed; the objective is then to minimize the maximum distance between a client and its assigned facility. If all the capacities ci ’s are identical, the problem becomes the well-studied uniform capacitated k -center problem for which constant-factor approximations are known [7, 22]. The additional choice of determining which capacity should be installed in which location makes our problem considerably different from this problem and the non-uniform generalizations studied thus far in literature. In fact, one of our contributions is in relating the heterogeneous problem to special-cases of the classical santa-claus problem. Using this connection, and by designing new algorithms for these special cases, we get the following results for Heterogeneous Cap- k -Center.