The metric uncapacitated facility location problem (UFL) enjoys a special stature in approximation algorithms as a testbed for various techniques. Two generalizations of UFL are capacitated facility location (CFL) and lower-bounded facility location (LBFL). In the former, every facility has a capacity which is the maximum demand that can be assigned to it, while in the latter, every open facility is required to serve a given minimum amount of demand. Both CFL and LBFL are approximable within a constant factor but their respective natural LP relaxations have an unbounded integrality gap. According to Shmoys and Williamson, the existence of a relaxation-based algorithm for CFL is one of the top 10 open problems in approximation algorithms. In this paper we give the first results on this problem. We provide substantial evidence against the existence of a good LP relaxation for CFL by showing unbounded integrality gaps for two families of strengthened formulations. The first family we consider is the hierarchy of LPs resulting from repeated applications of the lift-and-project Lov ' a sz-Schrijver procedure starting from the standard relaxation. We show that the LP relaxation for CFL resulting after @math rounds, where @math is the number of facilities in the instance, has unbounded integrality gap. Note that the Lov ' a sz-Schrijver procedure is known to yield an exact formulation for CFL in at most @math rounds. We also introduce the family of proper relaxations which generalizes to its logical extreme the classic star relaxation, an equivalent form of the natural LP. We characterize the integrality gap of proper relaxations for both LBFL and CFL and show a threshold phenomenon under which it decreases from unbounded to 1.
@cite_51 gave a 5-approximation algorithm, based on the standard LP, for the special case of where all facilities have the same opening cost. In the soft-capacitated facility location problem one is allowed to open multiple copies of the same facility. Work on this problem includes @cite_38 @cite_26 @cite_37 @cite_2 . As observed in @cite_59 a @math -approximation for yields a @math -approximation for the case with soft capacities. Mahdian, Ye and Zhang @cite_7 noticed a sharper tradeoff and obtained a @math -approximation. A tradeoff between the blowup of capacities and the cost approximation for was studied in @cite_20 . Bicriteria approximations for appeared in @cite_4 @cite_32 .
@cite_38 @cite_37 @cite_26 @cite_4 @cite_7 @cite_32 @cite_59 @cite_2 @cite_51 @cite_20
2028549267 2033647570 1854155592 1973529814
In the capacitated facility location problem with hard capacities, we are given a set of facilities, @math , and a set of clients @math in a common metric space. Each facility i has a facility opening cost f i and capacity u i that specifies the maximum number of clients that may be assigned to this facility. We want to open some facilities from the set @math and assign each client to an open facility so that at most u i clients are assigned to any open facility i. The cost of assigning client j to facility i is given by the distance c ij , and our goal is to minimize the sum of the facility opening costs and the client assignment costs. The only known approximation algorithms that deliver solutions within a constant factor of optimal for this NP-hard problem are based on local search techniques. It is an open problem to devise an approximation algorithm for this problem based on a linear programming lower bound (or indeed, to prove a constant integrality gap for any LP relaxation). We make progress on this question by giving a 5-approximation algorithm for the special case in which all of the facility costs are equal, by rounding the optimal solution to the standard LP relaxation. One notable aspect of our algorithm is that it relies on partitioning the input into a collection of single-demand capacitated facility location problems, approximately solving them, and then combining these solutions in a natural way. We present improved combinatorial approximation algorithms for the uncapacitated facility location problem. Two central ideas in most of our results are cost scaling and greedy improvement. We present a simple greedy local search algorithm which achieves an approximation ratio of @math in @math time. This also yields a bicriteria approximation tradeoff of @math for facility cost versus service cost which is better than previously known tradeoffs and close to the best possible. Combining greedy improvement and cost scaling with a recent primal-dual algorithm for facility location due to Jain and Vazirani, we get an approximation ratio of @math in @math time. This is very close to the approximation guarantee of the best known algorithm which is linear programming (LP)-based. Further, combined with the best known LP-based algorithm for facility location, we get a very slight improvement in the approximation factor for facility location, achieving @math . We also consider a variant of the capacitated facility location problem and present improved approximation algorithms for this. We present improved combinatorial approximation algorithms for the uncapacitated facility location and k-median problems. Two central ideas in most of our results are cost scaling and greedy improvement. We present a simple greedy local search algorithm which achieves an approximation ratio of 2.414+ spl epsiv in O spl tilde (n sup 2 spl epsiv ) time. This also yields a bicriteria approximation tradeoff of (1+ spl gamma , 1+2 spl gamma ) for facility cost versus service cost which is better than previously known tradeoffs and close to the best possible. Combining greedy improvement and cost scaling with a recent primal dual algorithm for facility location due to K. Jain and V. Vazirani (1999), we get an approximation ratio of 1.853 in O spl tilde (n sup 3 ) time. This is already very close to the approximation guarantee of the best known algorithm which is LP-based. Further combined with the best known LP-based algorithm for facility location, we get a very slight improvement in the approximation factor for facility location, achieving 1.728. We present improved approximation algorithms for capacitated facility location and a variant. We also present a 4-approximation for the k-median problem, using similar ideas, building on the 6-approximation of Jain and Vazirani. The algorithm runs in O spl tilde (n sup 3 ) time. In this paper we present a 1.52-approximation algorithm for the metric uncapacitated facility location problem, and a 2-approximation algorithm for the metric capacitated facility location problem with soft capacities. Both these algorithms improve the best previously known approximation factor for the corresponding problem, and our soft-capacitated facility location algorithm achieves the integrality gap of the standard linear programming relaxation of the problem. Furthermore, we will show, using a result of Thorup, that our algorithms can be implemented in quasi-linear time.