带惩罚的容错设施布局问题的近似算法

doi:10.15960/j.cnki.issn.1007-6093.2016.02.006

Abstract

Abstract:

In the fault-tolerant facility placement problem with penalties, we are given a set of customers and a set of sites, and connection costs between customers and sites. We assume that the connection costs satisfy the metric principle. Each customer has its service demands. We can open an unbounded number of different facilities at each site. Each customer can be either assigned to some different opened facilities in some sites to satisfy its demands or rejected by paying a penalty. The objective is to minimize the total cost of opening facilities and connecting those non-rejected customers to different open facilities, and the reject penalties. In this paper, we formulate the fault-tolerant facility placement problem with penalties as a linear integer programming and give its dual programming. Then we propose a 4-approximation algorithm based on rounding its linear programming and dual programming.

Key words: fault-tolerant facility placement problem, penalties, rounding, approximation algorithm

FANG Rui, LUO Wenchang. Approximation algorithm for the fault-tolerant facility placement problem with penalties[J]. Operations Research Transactions, doi: 10.15960/j.cnki.issn.1007-6093.2016.02.006.

References

[1] Shmoy D B, Tard\ddot{\mathrm o}s \acute{\mathrm E}, Aardal K I. Approximation algorithms for facility location problems [C]// Proceedings of STOC, New York: ACM, 1997, 265-274.

[2] Guha S, Khuller S. Greedy strikes back: improved facility location algorithms [J]. Journal of Algorithms, 1999, 31(1): 228-248.

[3] Sviridenko M. An improved approximation algorithm for the metric uncapacitated facility location problem [C]//Proceedings of the 9th International Conference on Integer Programming and Combinatorial Optimization, 2002, 240-257.

[4] Chudak F A, Shmoy D B. Improved approximation algorithm for the uncapacitated facility location problem [J]. SIAM Journal on Computing, 2003, 33(1): 1-25.

[5] Mahdian M, Ye Y, Zhang J. Approximation algorithms for metric facility location problems [J]. SIAM Journal on Computing, 2006, 36(2): 411-432.

[6] Byrka J, Aardal K. An optimal bifactor approximation algorithm for the metric uncapacitated facility location problem [J]. SIAM Journal on Computing, 2010, 39(6): 2212-2231.

[7] Li S. A 1.488 approximation algorithm for the uncapacitated facility location problem [J]. Information and Computation, 2013, 222: 45-58.

[8] Jain K, Vazirani V V. An approximation algorithm for the fault tolerant metric facility location problem [J]. Algorithmica, 2003, 38(3): 433-439.

[9] Guha S, Meyerson A, Munagala K. A constant factor approximation algorithms for the fault tolerant facility location problem [J]. Journal of Algorithms, 2003, 48(2): 433-439.

[10] Swamy C, Shmoy D B. Fault-tolerant facility location [J]. ACM Transactions on Algorithms, 2008, 4(4): 1-27.

[11] Byrka J, Srinivasan A, Swamy C. Fault-tolerant facility location: a randomized dependent LP-rounding algorithm [C]//Proceedings of the 17th International Conference on Integer Programming and Combinatorial Optimization, 2010, 244-257.

[12] Xu S, Shen H. The fault-tolerant facility allocation problem [C]//Proceedings of the 20th International Symposium on Algorithms and Computation, 2009, 689-698.

[13] Yan L, Chrobak M. Approximation algorithms for the fault-tolerant facility placement problem [J]. Information Processing Letters, 2011, 111: 545-549.

[14] Shao J, Xu D. An Approximation algorithm for the stochastic fault-tolerant facility placement problem [J]. Opeartions Research Transaction, 2012, 16: 13-20.

[15] Xu G, Xu J. An LP rounding algorithm for approximating uncapacitated facility location problem with penalties [J]. Information Processing Letters, 2005, 94: 119-123.

Approximation algorithm for the fault-tolerant facility placement problem with penalties

PDF

Knowledge

Cited

Abstract

Cite this article

share this article

References

Related Articles 15

Recommended Articles

Metrics

Comments

[1]	ZHANG Yuzhong. A survey on job scheduling with rejection [J]. Operations Research Transactions, 2020, 24(2): 111-130.
[2]	LIU Xiaoxia, YU Shanshan, LUO Wenchang. Approximation algorithms for single machine parallelbatch scheduling with release dates subject to the number of rejected jobs not exceeding a given threshold [J]. Operations Research Transactions, 2020, 24(1): 131-139.
[3]	WANG Yizhan, ZHANG An, CHEN Yong, CHEN Guangting. An approximation algorithm for reclaimer scheduling [J]. Operations Research Transactions, 2020, 24(1): 147-154.
[4]	ZHANG Guochuan, CHEN Lin. The load balancing problem [J]. Operations Research Transactions, 2019, 23(3): 1-14.
[5]	JIANG Yanjun, XU Dachuan, ZHANG Dongmei. An approximation algorithm for the squared metric dynamic facility location problem [J]. Operations Research Transactions, 2018, 22(3): 49-58.
[6]	WANG Yishui, XU Dachuan, WU Chenchen. A semidefinite programming rounding algorithm for correlation clustering problem [J]. Operations Research Transactions, 2018, 22(1): 67-76.
[7]	CHEN Guangting, CHEN Lei, ZHANG An, CHEN Yong. Approximation algorithms for two-machine flow shop scheduling with an outsourcing option [J]. Operations Research Transactions, 2016, 20(4): 109-114.
[8]	ZHONG Weiya, MA Xiaoru. A no-wait flowshop scheduling problem with processing flexibility and transportation [J]. Operations Research Transactions, 2016, 20(4): 93-101.
[9]	SUN Ting, LI Gaidi, XU Wenqing. Approximation algorithms for max cut and max bisection problems using semi-definite programming relaxations [J]. Operations Research Transactions, 2016, 20(3): 21-32.
[10]	YAN Lincheng,XIAO Han,ZHAO Hongjuan,SUN Xiaoqi. An approximation algorithm for reliable facility location problem [J]. Operations Research Transactions, 2015, 19(4): 14-24.
[11]	FAN Jing, ZHANG Feng. Supply chain scheduling problem with multiple unavailability intervals on a single machine [J]. Operations Research Transactions, 2015, 19(3): 116-122.
[12]	WANG Ying, WANG Fengmin, XU Dachuan, XU Wenqing. Approximation algorithms for the priority facility location problem with submodular penalties [J]. Operations Research Transactions, 2015, 19(2): 1-14.
[13]	XU Dachuan, WAN Wei, WU Chenchen, XU Wenqing. A primal-dual approximation algorithm for stochastic fault-tolerant facility location problem [J]. Operations Research Transactions, 2014, 18(2): 17-28.
[14]	LI Zhening, LING Chen, WANG Yiju, YANG Qingzhi. Some advances in tensor analysis and polynomial optimization [J]. Operations Research Transactions, 2014, 18(1): 134-148.
[15]	CHEN Xujin, XU Dachuan, ZHANG Guochuan. New perspectives of several fundamental problems in combinatorial optimization [J]. Operations Research Transactions, 2014, 18(1): 149-158.