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 c_i'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. 1. A quasi-polynomial time O(log n/ε)-approximation where every capacity is violated by (1 + ε) factor. 2. A polynomial time O(1)-approximation where every capacity is violated by an O(log n) factor. We get improved results for the soft-capacities version where we can place multiple facilities in the same location.
展开▼
