随机容错设施布局问题的近似算法

Abstract

Abstract: In the deterministic fault-tolerant facility placement problem (FTFP), we are given a set of locations and a set of clients. We can open any number of different facilities with the same opening cost at each location. Each client j has an integer requirement r_j. Connecting client j to different facilities at the same location is permitted. The objective is to open some facilities and connect each client j to r_j different facilities such that the total cost is minimized. In this paper, we consider the two-stage stochastic fault-tolerant facility placement problem (SFTFP) with recourse in which the set of clients are unknown in advance. But there are finite scenarios materialized by a probability distribution. Each scenario specifies a subset of clients to be assigned. Moreover, each facility has two kinds of opening cost. In the first stage, we open a subset of facilities according to the stochastic information of the clients. In the second stage, we can open additional number of facilities when the actual information of the clients is revealed. We give a linear integral program and an LP-rounding based 5-approximation algorithm for the SFTFP.

Key words: facility placement problem, approximation algorithm, LP-rounding

SHAO Jia-Ting, Xu-Da-Chuan. An Approximation Agorithm for the Stochastic Fault-Tolerant Fcility Placement Problem[J]. Operations Research Transactions, 2012, 16(1): 13-20.

References

Jain K, Mahdian M, Markakis E, et al. Greedy facility location algorithms analyzed using dual fitting with factor-revealing LP [J]. Journal of the ACM, 2003, 50(6): 795-824.
Jain K, Vazirani V V. Approximation algorithms for metric facility location and k-median problems using the primal-dual schema and Lagrangian relaxation [J]. Journal of the ACM, 2001, 48(2): 274-296.
Mahdian M, Ye Y Y, Zhang J W. Approximation algorithms for metric facility location problems [J]. SIAM Journal on Computing, 2006, 36(2): 411-432.
Li S. A 1.488 approximation algorithm for the uncapacitated facility location problem [C]// Luca Aceto, Proceedings of ICALP, Part II, Switzerland: Springer, 2011, 77-88.
Guha S, Khuller S. Greedy strikes back: improved facility location algorithms [J]. Journal of Algorithms, 1999, 31(1): 228-248.
Byrka J, Aardal K I, An optimal bifactor approximation algorithm for the metric uncapacitated facility location problem [J]. SIAM Journal on Computing, 2010, 39(6): 2212-2231.
Shmoys D B, Tardos E, Aardal K I. Approximation algorithms for facility location problems (extended abstract) [C]// F. Tom Leighton, Peter Shor, Proceedings of STOC, Texas: ACM New York, 1997, 265-274.
Sviridenko M. An improved approximation algorithm for the metric uncapacitated facility location problem [C]// William J, Proceedings of IPCO, Cambridge: Springer, 2002, 240-257.
Ageev A, Ye Y Y, Zhang J W. Improved combinatorial apporximation algorithms for the k-level facility location problem [J]. SIAM Journal on Discrete Mathematics, 2004, 18(1): 207-217.
Chen X J, Chen B. Approximation algorithms for soft-capacitated facility location in capacitated network design [J]. Algorithmica, 2007, 53(3): 263-297.
Du D D, Lu R X, Xu D C. A primal-dual approximation algorithm for the facility location problem with submodular penalties [J]. Algorithmica, 2012, 63(1-2): 191-200.
Shu J. An efficient greedy heuristic for warehouse-retailer network design optimization [J]. Transportation Science, 2010, 44(2): 183-192.
Shu J, Teo C P, Max Shen Z J. Stochastic transportation-inventory network design problem [J]. Operations Research, 2005, 53(1): 48-60.
Zhang P. A new approximation algorithm for the k-facility location problem [J]. Theoretical Computer Science, 2007, 384(1): 126-135.
Jain K, Vazirani V V. An approximation algorithms for the fault tolerant metric facility location problem [J]. Algorithmica, 2003, 38(3): 433-439.
Byrka J, Srinivasan A, Swamy C. Fault-tolerant facility location: a randomized dependent LP-rounding algorithm [C]// Friedrich Eisenbrand and F. Bruce, Proceedings of IPCO, Switzerland: Springer, 2010, 244-257.
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): 449-420.
Swamy C, Shmoys D B. Fault-tolerant facility location [J]. ACM Transactions on Algorithms, 2008, 4(4), Article 51.
Xu S H, Shen H. The fault-tolerant facility allocation problem [C]// Yingfei Dong, Ding-Zhu Du and Oscar Ibarra, Proceedings of ISAAC, Hawaii: Springer, 2009, 689-698.
Ravi R, Sinha A. Hedging uncertainty: approximation algorithms for stochastic optimization problems [J]. Mathmatical Programming, 2006, 108(1): 97-114.
Yan L, Chrobak M. Approximation algorithms for the fault tolerant facility placement problem [J]. Information Processing Letters, 2011, 111(11): 545-549.

[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]	FANG Rui, LUO Wenchang. Approximation algorithm for the fault-tolerant facility placement problem with penalties [J]. Operations Research Transactions, 2016, 20(2): 69-78.
[11]	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.
[12]	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.
[13]	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.
[14]	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.
[15]	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.

An Approximation Agorithm for the Stochastic Fault-Tolerant Fcility Placement Problem

PDF

Knowledge

Abstract

Cite this article

share this article

References

Related Articles 15

Recommended Articles

Metrics

Comments