Improved approximation algorithms for the uncapacitated facility location problem

被引:172
作者
Chudak, FA [1 ]
Shmoys, DB
机构
[1] Cornell Univ, Sch Operat Res & Ind Engn, Ithaca, NY 14853 USA
[2] Swiss Fed Inst Technol, Swiss Fed Inst Technol, Inst Operat Res, Zurich, Switzerland
[3] Cornell Univ, Dept Comp Sci, Ithaca, NY 14853 USA
关键词
facility location; approximation algorithms; randomized rounding;
D O I
10.1137/S0097539703405754
中图分类号
TP301 [理论、方法];
学科分类号
081202 ;
摘要
We consider the uncapacitated facility location problem. In this problem, there is a set of locations at which facilities can be built; a fixed cost f(i) is incurred if a facility is opened at location i. Furthermore, there is a set of demand locations to be serviced by the opened facilities; if the demand location j is assigned to a facility at location i, then there is an associated service cost proportional to the distance between i and j, c(ij). The objective is to determine which facilities to open and an assignment of demand points to the opened facilities, so as to minimize the total cost. We assume that the distance function c is symmetric and satisfies the triangle inequality. For this problem we obtain a (1 + 2/e)-approximation algorithm, where 1 + 2/e approximate to 1.736, which is a significant improvement on the previously known approximation guarantees. The algorithm works by rounding an optimal fractional solution to a linear programming relaxation. Our techniques use properties of optimal solutions to the linear program, randomized rounding, as well as a generalization of the decomposition techniques of Shmoys, Tardos, and Aardal [Proceedings of the 29th ACM Symposium on Theory of Computing, El Paso, TX, 1997, pp. 265-274].
引用
收藏
页码:1 / 25
页数:25
相关论文
共 31 条
[1]  
AGEEV AA, 1997, UNPUB APPROXIMATION
[2]  
[Anonymous], 1999, 40 ANN S FDN COMP SC
[3]   Polynomial time approximation schemes for Euclidean traveling salesman and other geometric problems [J].
Arora, S .
JOURNAL OF THE ACM, 1998, 45 (05) :753-782
[4]  
Arora S., 1998, Proceedings of the Thirtieth Annual ACM Symposium on Theory of Computing, P106, DOI 10.1145/276698.276718
[5]   INTEGER PROGRAMMING - METHODS, USES, COMPUTATION [J].
BALINSKI, ML .
MANAGEMENT SCIENCE, 1965, 12 (03) :253-313
[6]  
Chudak FA, 1998, LECT NOTES COMPUT SC, V1412, P180
[7]   LOCATION OF BANK ACCOUNTS TO OPTIMIZE FLOAT - ANALYTIC STUDY OF EXACT AND APPROXIMATE ALGORITHMS [J].
CORNUEJOLS, G ;
FISHER, ML ;
NEMHAUSER, GL .
MANAGEMENT SCIENCE, 1977, 23 (08) :789-810
[8]  
Cornuejols G, 1990, DISCRETE LOCATION TH, P119
[9]  
Erdos P., 1973, Journal of Combinatorial Theory, Series A, V14, P298, DOI 10.1016/0097-3165(73)90005-8
[10]   A threshold of in n for approximating set cover [J].
Feige, U .
JOURNAL OF THE ACM, 1998, 45 (04) :634-652