×

Approximation algorithms for \(k\)-level stochastic facility location problems. (English) Zbl 1384.90087

Summary: In the \(k\)-level facility location problem (FLP), we are given a set of facilities, each associated with one of \(k\) levels, and a set of clients. We have to connect each client to a chain of opened facilities spanning all levels, minimizing the sum of opening and connection costs. This paper considers the \(k\)-level stochastic FLP, with two stages, when the set of clients is only known in the second stage. There is a set of scenarios, each occurring with a given probability. A facility may be opened in any stage, however, the cost of opening a facility in the second stage depends on the realized scenario. The objective is to minimize the expected total cost. For the stage-constrained variant, when clients must be served by facilities opened in the same stage, we present a \((4-o(1))\)-approximation, improving on the 4-approximation by Z. Wang et al. [Oper. Res. Lett. 38, No. 5, 386–389 (2010; Zbl 1202.90178); ibid. 39, No. 2, 160–161 (2011; Zbl 1218.90106)] for each \(k\). In the case with \(k=2,3\), the algorithm achieves factors 2.56 and 2.78, resp., which improves the \((3+\epsilon)\)-approximation for \(k=2\) by C. Wu et al. [Theor. Comput. Sci. 562, 213–226 (2015; Zbl 1303.68158)]. For the non-stage-constrained version, we give the first approximation for the problem, achieving a factor of \(3.495\) for the case with \(k = 2\), and \(2k-1+o(1)\) in general.

MSC:

90C27 Combinatorial optimization
90C15 Stochastic programming
90C59 Approximation methods and heuristics in mathematical programming
PDFBibTeX XMLCite
Full Text: DOI

References:

[1] Aardal K, Chudak FA, Shmoys DB (1999) A 3-approximation algorithm for the k-level uncapacitated facility location problem. Inform Process Lett 72(5-6):161-167 · Zbl 0994.90090 · doi:10.1016/S0020-0190(99)00144-1
[2] Ageev AA (2002) Improved approximation algorithms for multilevel facility location problems. Oper Res Lett 30(5):327-332 · Zbl 1010.90038 · doi:10.1016/S0167-6377(02)00162-1
[3] Ageev AA, Ye Y, Zhang J (2003) Improved combinatorial approximation algorithms for the k-level facility location problem. In: Proc. 30th Int. Colloquium on Automata, Languages and Programming, pp 145-156 · Zbl 1060.90677
[4] Beale EML (1955) On minimizing a convex function subject to linear inequalities. J R Stat Soc Ser B 17:173-184 · Zbl 0068.13701
[5] Byrka J, Aardal K (2010) An optimal bifactor approximation algorithm for the metric uncapacitated facility location problem. SIAM J Comput 39(6):2212-2231 · Zbl 1205.90173 · doi:10.1137/070708901
[6] Byrka J, Li S, Rybicki B (2016) Improved approximation algorithm for k-level uncapacitated facility location problem (with penalties). Theory Comput Syst 58(1):19-44 · Zbl 1336.68290 · doi:10.1007/s00224-014-9575-3
[7] Byrka J, Rybicki B (2012) Improved LP-rounding approximation algorithm for k-level uncapacitated facility location. In: Proc. 39th Int. Colloquium on Automata, Languages, and Programming, pp 157-169 · Zbl 1272.90019
[8] Chudak FA, Shmoys DB (2003) Improved approximation algorithms for the uncapacitated facility location problem. SIAM J Comput 33(1):1-25 · Zbl 1044.90056 · doi:10.1137/S0097539703405754
[9] Dantzig GB (1955) Linear programming under uncertainty. Manage Sci 1:197-206 · Zbl 0995.90589 · doi:10.1287/mnsc.1.3-4.197
[10] Dye S, Stougie L, Tomasgard A (1999) The stochastic single resourceservice-provision problem. Naval Res Logist 50(8):869-887 (2003). Also appeared as “The stochastic single nodeservice provision problem”, COSOR-Memorandum 99-13, Dept. ofMathematics and Computer Science, Eindhoven Technical University, Eindhoven · Zbl 1055.90093
[11] Guha S, Khuller S (1999) Greedy strikes back: improved facility location algorithms. Jf Algorithms 31(1):228-248 · Zbl 0928.68137 · doi:10.1006/jagm.1998.0993
[12] INFORMS: Section on Location Analysis (2015). https://www.informs.org/Community/SOLA · Zbl 1010.90038
[13] Krishnaswamy R, Sviridenko M (2012) Inapproximability of the multi-level uncapacitated facility location problem. In: Proc. 23rd Annual ACM-SIAM Symposium on Discrete Algorithms, pp 718-734 · Zbl 1423.68195
[14] Mahdian M (2004) Facility location and the analysis of algorithms through factor-revealing programs. Ph.D. thesis, Massachusetts Institute of Technology
[15] Mahdian M, Ye Y, Zhang J (2002) Improved approximation algorithms for metric facility location problems. In: Proc. 5th Int. Workshop on Approximation Algorithms for Combinatorial Optimization, pp 229-242 · Zbl 1013.90115
[16] Ravi R, Sinha A (2006) Hedging uncertainty: approximation algorithms for stochastic optimization problems. Math Program 108(1):97-114 · Zbl 1098.90046 · doi:10.1007/s10107-005-0673-5
[17] Shmoys DB, Tardos E, Aardal K (1997) Approximation algorithms for facility location problems (extended abstract). In: Proc. 29th Annual ACM Symposium on the Theory of Computing, pp 265-274 · Zbl 0962.68008
[18] Srinivasan A (2007) Approximation algorithms for stochastic and risk-averse optimization. In: Proc. 18th Annual ACM-SIAM Symposium on Discrete Algorithms, pp 1305-1313 · Zbl 1302.68325
[19] Swamy C, Shmoys DB (2006) Approximation algorithms for 2-stage stochastic optimization problems. SIGACT News 37(1):33-46 · Zbl 1177.90302 · doi:10.1145/1122480.1122493
[20] Wang Z, Du D, Gabor AF, Xu D (2010) An approximation algorithm for the k-level stochastic facility location problem. Oper Res Lett 38(5):386-389 · Zbl 1202.90178 · doi:10.1016/j.orl.2010.04.010
[21] Wang Z, Du D, Gabor AF, Xu, D (2011) Erratum to: “An approximation algorithm for the k-level stochastic facility location problem” [Oper. Res. Lett. 38(2010) 386-389]. Oper Res Lett 39(2):160-161 · Zbl 1218.90106
[22] Wang, Z.; Du, D.; Xu, D.; Chen, B. (ed.), A primal-dual approximation algorithm for the k-level stochastic facility location problem, No. 6124, 253-260 (2010), Berlin Heidelberg · Zbl 1286.90086 · doi:10.1007/978-3-642-14355-7_26
[23] Wu C, Du D, Xu D (2015) Primal-dual approximation algorithm for the two-level facility location problem via a dual quasi-greedy approach. Theor Comput Sci 562:213-226 · Zbl 1303.68158 · doi:10.1016/j.tcs.2014.09.045
[24] Ye, Y.; Zhang, J.; Cheng, M. (ed.); Li, Y. (ed.); Du, DZ (ed.), An approximation algorithm for the dynamic facility location problem, No. 18, 623-637 (2006), US · Zbl 1115.90034 · doi:10.1007/0-387-29026-5_22
[25] Zhang J (2006) Approximating the two-level facility location problem via a quasi-greedy approach. Math Program 108(1):159-176 · Zbl 1142.90440 · doi:10.1007/s10107-006-0704-x
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.