New Approximation Algorithms for the Unsplittable Capacitated Facility Location Problem

摘要

In this paper, we consider the Unsplittable (hard) Capacitated Facility Location Problem (UCFLP) with uniform capacities and present some new approximation algorithms for it. This problem is a generalization of the classical facility location problem where each facility can serve at most u units of demand and each client must be served by exactly one facility. It is known that it is NP-hard to approximate this problem within any factor without violating the capacities. So we consider bicriteria (α,β)-approximations where the algorithm returns a solution whose cost is within factor α of the optimum and violates the capacity constraints within factor β. We present a framework for designing bicriteria approximation algorithms and show two new approximation algorithms with factors (10.173,3/2) and (30.432,4/3). These are the first algorithms with constant approximation in which the violation of capacities is below 2. The heart of our algorithms is a reduction from the UCFLP to a restricted version of the problem. One feature of this reduction is that any (O(1), 1 + ε-approximation for the restricted version implies an (0(1), 1 + ε)-approximation for the UCFLP for any constant ε > 0 and we believe our techniques might be useful towards rinding such approximations or perhaps (f(ε),1 + ε)-approximation for the UCFLP for some function f. In addition, we present a quasi-polynomial time (1 + ε, 1 + ε)-approximation for the (uniform) UCFLP in Euclidean metrics, for any constant ε > 0.