Approximating Capacitated K-median with (1 + Ε)K Open Facilities

In the capacitated k-median (CKM) problem, we are given a set F of facilities, each facility i F with a capacity ui, a set C of clients, a metric d over F C and an integer k. The goal is to open k facilities in F and connect the clients C to the open facilities such that each facility i is connected by at most ui 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 + e. This generalizes the result of [Li15], which only works for the uniform capacitated case. Moreover, the approximation ratio we obtain is O([EQUATION] log [EQUATION]), which is an exponential improvement over the ratio of exp (O([EQUATION])) in [Li15]. The natural LP relaxation for the problem, which almost all previous algorithms for CKM are based on, has unbounded integrality gap even if (2 - e)k 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.