An improved approximation algorithm for uncapacitated facility location problem with penalties

被引:48
作者
Xu, Guang [1 ]
Xu, Jinhui [1 ]
机构
[1] SUNY Buffalo, Dept Comp Sci & Engn, Buffalo, NY 14260 USA
基金
美国国家科学基金会;
关键词
Algorithms; Approximation algorithms; Facility location problem; Outliers; LP;
D O I
10.1007/s10878-007-9127-8
中图分类号
TP39 [计算机的应用];
学科分类号
081203 ; 0835 ;
摘要
In this paper, we consider an interesting variant of the classical facility location problem called uncapacitated facility location problem with penalties (UFLWP for short) in which each client is either assigned to an opened facility or rejected by paying a penalty. The UFLWP problem has been effectively used to model the facility location problem with outliers. Three constant approximation algorithms have been obtained (Charikar et al. in Proceedings of the Symposium on Discrete Algorithms, pp. 642-651, 2001; Jain et al. in J. ACM 50(6):795-824, 2003; Xu and Xu in Inf. Process. Lett. 94(3):119-123, 2005), and the best known performance ratio is 2. The only known hardness result is a 1.463-inapproximability result inherited from the uncapacitated facility location problem (Guha and Khuller in J. Algorithms 31(1):228-248, 1999). In this paper, We present a 1.8526-approximation algorithm for the UFLWP problem. Our algorithm significantly reduces the gap between known performance ratio and the inapproximability result. Our algorithm first enhances the primal-dual method for the UFLWP problem (Charikar et al. in Proceedings of the Symposium on Discrete Algorithms, pp. 642-651, 2001) so that outliers can be recognized more efficiently, and then applies a local search heuristic (Charikar and Guha in Proceedings of the 39th IEEE Symposium on Foundations of Computer Science, pp. 378-388, 1999) to further reduce the cost for serving those non-rejected clients. Our algorithm is simple and can be easily implemented.
引用
收藏
页码:424 / 436
页数:13
相关论文
共 14 条
[1]  
[Anonymous], LECT NOTES COMPUTER
[2]  
Arya V., 2001, P 33 ANN ACM S THEOR, P21
[3]  
Charikar M, 2001, SIAM PROC S, P642
[4]  
Charikar M., 1999, PROC 40 ANN IEEE S F, P378
[5]  
Chudak FA, 1999, LECT NOTES COMPUT SC, V1610, P99
[6]  
Chudak Fabian., 1999, P 10 ANN ACM SIAM S, P875
[7]   A constant factor approximation algorithm for the fault-tolerant facility location problem [J].
Guha, S ;
Meyerson, A ;
Munagala, K .
JOURNAL OF ALGORITHMS-COGNITION INFORMATICS AND LOGIC, 2003, 48 (02) :429-440
[8]   Greedy strikes back: Improved facility location algorithms [J].
Guha, S ;
Khuller, S .
JOURNAL OF ALGORITHMS-COGNITION INFORMATICS AND LOGIC, 1999, 31 (01) :228-248
[9]   Greedy facility location algorithms analyzed using,dual fitting with factor-revealing LP [J].
Jain, K ;
Mahdian, M ;
Markakis, E ;
Saberi, A ;
Vazirani, VV .
JOURNAL OF THE ACM, 2003, 50 (06) :795-824
[10]   Approximation algorithms for metric facility location and k-median problems using the primal-dual schema and Lagrangian relaxation [J].
Jain, K ;
Vazirani, VV .
JOURNAL OF THE ACM, 2001, 48 (02) :274-296