LP-based approximation algorithms for capacitated facility location
成果类型：
Article
署名作者：
Levi, Retsef; Shmoys, David B.; Swamy, Chaitanya
署名单位：
Massachusetts Institute of Technology (MIT); Cornell University; Cornell University; University of Waterloo
刊物名称：
MATHEMATICAL PROGRAMMING
ISSN/ISSBN：
0025-5610
DOI：
10.1007/s10107-010-0380-8
发表日期：
2012
页码：
365-379
关键词：
摘要：
In the capacitated facility location problem with hard capacities, we are given a set of facilities, F, and a set of clients D 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 F and assign each client to an open facility so that at most ui 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.