Approximation algorithm for two-stage stochastic fault-tolerant facility location problem

Li Zhang; Qiaoliang Li

doi:10.3934/jimo.2024146

Article Contents

2025, Volume 21, Issue 3: 1735-1748. Doi: 10.3934/jimo.2024146

This issue Previous Article Incentive contract for high-quality recycling of construction waste: Considering fairness concerns and information asymmetry Next Article A review of algorithms for distributionally robust optimization using statistical distances

Approximation algorithm for two-stage stochastic fault-tolerant facility location problem

Li Zhang^1, and
Qiaoliang Li^2, ,

1.
College of Information and Intelligence, Hunan Agricultural University, Changsha, Hunan 410128, China
2.
School of Mathematics and Statistics, Hunan Normal University, Changsha, Hunan 410081, China

^*Corresponding author: Qiaoliang Li
^*Corresponding author: Qiaoliang Li

Received: February 2024

Revised: August 2024

Early access: October 2024

Published: March 2025

The second author is supported by [NSFC grant 12071126].

Abstract / Introduction Full Text(HTML) Figure(2) Related Papers Cited by

Abstract

In this paper, we consider the two-stage stochastic fault-tolerant facility location problem with uniform connectivity demand (2-SFTFLPUCD). We present the currently best known approximation ratio 1.8526 for 2-SFTFLPUCD. Initially, we demonstrate a stronger result of the 3-approximation algorithm based on analysis of the sum of opening and connection cost. Subsequently, we seed a greedy augmentation algorithm with the solution of a 3-approximation algorithm to yield an improved approximation ratio.

Keywords:

Mathematics Subject Classification: Primary: 90C10; Secondary: 90C27.

Citation:

Full Text(HTML)

Figure 1. The indirectly saturated client in 9, (1)

Download: Full-size image PowerPoint slide

Figure 2. The indirectly saturated client in 9, (2)

Download: Full-size image PowerPoint slide

Related Papers

Cited by

References

[1]	S. Guha and S. Khuller, Greedy strikes back: Improved facility location algorithms, Journal of Algorithms, 31 (1999), 228-248. doi: 10.1006/jagm.1998.0993.
[2]	K. Jain and V. V. Vazirani, Approximation algorithms for metric facility location and $k$-median problems using the primal-dual schema and Lagrangian relaxation, Journal of the ACM, 48 (2001), 274-296. doi: 10.1145/375827.375845.
[3]	S. Ji, D. Xu, D. Du and Y. Wang, LP-rounding approximation algorithms for two-stage stochastic fault-tolerant facility location problem, Applied Mathematical Modelling, 58 (2018), 76-85. doi: 10.1016/j.apm.2017.12.009.
[4]	S. Li, A 1.488 approximation algorithm for the uncapacitated facility location problem, Information and Computation, 222 (2013), 45-58. doi: 10.1016/j.ic.2012.01.007.
[5]	J.-H. Lin and J. S. Vitter, $\epsilon$-approximations with minimum packing constraint violation (extended abstract), in: Proceedings of the 24th Annual ACM Symposium on Theory of Computing, ACM, Victoria, British Columbia, Canada, 1992, 771-782. doi: 10.1145/129712.129787.
[6]	M. Mahdian, Facility Location and the Analysis of Algorithms Through Factor-Revealing Programs, Ph.D. thesis, Massachusetts Institute of Technology, Cambridge (2004).
[7]	R. Ravi and A. Sinha, Hedging uncertainty: Approximation algorithms for stochastic optimization problems, Mathematical Programming, 108 (2006), 97-114. doi: 10.1007/s10107-005-0673-5.
[8]	D. B. Shmoys, É. Tardos and K. Aardal, Approximation algorithms for facility location problems (extended abstract), in: Proceedings of the Twenty-Ninth Annual ACM Symposium on the Theory of Computing, ACM, El Paso, Texas, USA, 1997, 265-274. doi: 10.1145/258533.258600.
[9]	A. Srinivasan, Approximation algorithms for stochastic and risk-averse optimization, in: Proceedings of the Eighteenth Annual ACM-SIAM Symposium on Discrete Algorithms, ACM, New York, 2007, 1305-1313.
[10]	C. Wu, D. Xu and J. Shu, An approximation algorithm for the stochastic fault-tolerant facility location problem, Journal of the Operations Research Society of China, 1 (2013), 511-522. doi: 10.1007/s40305-013-0034-7.
[11]	D. C. Xu, W. Wan, C. C. Wu and W. Q. Xu, A primal-dual approximation algorithm for stochastic fault-tolerant facility location problem, Operations Research Transactions, 18 (2014), 17-28.
[12]	Y. Ye and J. Zhang, An approximation algorithm for the dynamic facility location problem, In Combinatorial Optimization in Communication Networks, Springer US, Boston, MA, 2006, 623-637. doi: 10.1007/0-387-29026-5_22.