Approximating capacitated κ-median with (l + ∈)k open facilities

In the capacitated κ-median (CKM) problem, we are given a set F of facilities, each facility i ∈ F with a capacity U_i, a set C of clients, a metric d over FUC and an integer κ. The goal is to open κ facilities in F and connect the clients C to the open facilities such that each facility i is connected by at most U_i clients, so as to minimize the total connection cost. In this paper, we give the first constant approximation for CKM, that only violates the cardinality constraint by a factor of 1 + ∈. This generalizes the result of [Lil5], which only works for the uniform capacitated case. Moreover, the approximation ratio we obtain is O(1/2_∈log 1/∈), which is an exponential improvement over the ratio of exp (O(1/2_∈)) in [Lil5]. The natural LP relaxation for the problem, which almost all previous algorithms for CKM are based on, has unbounded integrality gap even if (2-∈)κ facilities can be opened. We introduce a novel configuration LP for the problem, that overcomes this integrality gap. On the downside, each facility may be opened twice by our algorithm.