随机容错设施选址问题的原始-对偶近似算法

Abstract

Abstract: In this paper, we consider the two-stage stochastic fault-tolerant facility location problem with uniform connectivity requirement where the clients to be served are only revealed at stage two (thus unknown at stage one). The facilities may be opened at either stage, with possibly different opening costs, depending on the stage and the set of clients to be served (called a scenario). Each client to be served in such a scenario has to be connected to r \geq 1 distinct facilities. Given all possible scenarios and the corresponding probabilities, the objective is to determine two subsets of facilities to be opened at the two stages and to connect the clients in the realized scenario to r distinct opened facilities such that the total expected opening and connection cost is minimized. Based on the special structure of the problem, we offer a primal-dual (combinatorial) 3-approximation algorithm.

Key words: facility location problem, stochastic demands, fault-tolerance, approximation algorithm, primal-dual algorithm

CLC Number:

O221.7

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.

References

Dean B C, Goemans M X, Vondrak J. Approximating the stochastic knapsack problem: the benefit of adaptivity [J]. Mathematics of Operations Research, 2008, 33: 945-964.
Dhamdhere K, Goyal V, Ravi R, Singh M. How to pay, come what may: approximation algorithms for demand-robust covering problems [C]//Proceedings of 46 th Annual IEEE Symposium on Foundations of Computer Science, Pittsburgh, 2005, 367-378.
Kumar A, Gupta A, Roughgarden T. A constant factor approximation algorithm for the multicommodity rent-or-buy problem [C]//Proceedings of 43 th Annual IEEE Symposium on Foundations of Computer Science, Vancouver, 2002, 333-342.
Shmoys D B, Swamy C. Sampling-based approximation algorithms for multi-stage stochastic optimization [C]//Proceedings of 46 th Annual IEEE Symposium on Foundations of Computer Science, Pittsburgh, 2005, 357-366.
Shmoys D B, Swamy C. Algorithms column：approximation algorithms for 2-stage stochastic optimization problems [J]. ACM SIGACT News, 2006, 37: 33-46.

Swamy C. Approximation algorithms for clustering problems [D]. Ithaca: Cornell University, 2006.
Ye Y, Zhang J. An approximation algorithm for the dynamic facility location problem [M]//Combinatorial Optimization in Communication Networks, New York: Kluwer Academic Publishers, 2005, 623-637.
Ravi R, Sinha A. Hedging uncertainty: approximation algorithms for stochastic optimization problems [J]. Mathematical Programming, 2006, 108: 97-114.
Sinha A. Location, location, location and location [D]. Pittsburgh: Carnegie Mellon University, 2004.
Mahdian M. Facility location and the analysis of algorithms through factor-revealing programs [D]. Cambridge: Massachusetts Institute of Technology, 2004.
Srinivansan A. Approximation algorithms for stochastic and risk-averse optimization [C]//Proceedings of ACM-SIAM Symposium on Discrete Algorithms, New Orleans , 2007, 1305-1313.
Jain K, Vazirani V V. An approximation algorithm for the fault tolerant metric facility location problem [J]. Algorithmica, 2003, 38: 433-439.
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: 274-296.
Guha S, Meyerson A, Munagala K. Improved algorithms for fault-tolerant facility location [J]. Journal of Algorithms, 2003, 8: 429-440.
Shmoys D B, Tardos E, Aardal K I. Approximation algorithms for facility location problems [C]//Proceedings of 29 th Annual ACM Symposium on the Theory of Computing, Texas, 1997, 265-274.
Swamy C, Shmoys D B. Fault-tolerant facility location [J]. ACM Transactions on Algorithms, 2008, 4: 51.
Byrka J, Srinivasan A, Swamy C. Fault-tolerant facility location: a randomized dependent LP-rounding algorithm [C]//Proceedings of 14 th International Conference on Integer Programming and Combinatorial Optimization, Lausanne, 2010, 244-257.
Bumb A. Approximation algorithms for facility location problems [D]. Enschede: Twente University, 2002.
Guha S, Khuller S. Greedy strike back: improved facility location algorithms [J]. Journal of Algorithms, 1999, 31: 228-248.

[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]	YANG Muming, HUANG Yakui, DAI Yuhong. Linear relaxation solution based heuristics for a class of multi-product facility location problems [J]. Operations Research Transactions, 2019, 23(3): 15-26.
[6]	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.
[7]	WANG Yishui, XU Dachuan, WU Chenchen. A semidefinite programming rounding algorithm for correlation clustering problem [J]. Operations Research Transactions, 2018, 22(1): 67-76.
[8]	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.
[9]	ZHONG Weiya, MA Xiaoru. A no-wait flowshop scheduling problem with processing flexibility and transportation [J]. Operations Research Transactions, 2016, 20(4): 93-101.
[10]	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.
[11]	FANG Rui, LUO Wenchang. Approximation algorithm for the fault-tolerant facility placement problem with penalties [J]. Operations Research Transactions, 2016, 20(2): 69-78.
[12]	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.
[13]	AN Bang,CHENG Peng. An algorithm for a class of uncapacitated facility location problem based on branch-and-cut method [J]. Operations Research Transactions, 2015, 19(4): 1-13.
[14]	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.
[15]	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.

A primal-dual approximation algorithm for stochastic fault-tolerant facility location problem

PDF

Knowledge

Abstract

Cite this article

share this article

References

Related Articles 15

Recommended Articles

Metrics

Comments