A primal-dual approximation algorithm for stochastic facility location problem with service installation costs

Abstract

We consider the stochastic version of the facility location problem with service installation costs. Using the primal-dual technique, we obtain a 7-approximation algorithm.

Keywords

Stochastic facility location problem / primal-dual / approximation algorithm

References

[1] Ageev A, Ye Y, Zhang J. Improved combinatorial approximation algorithms for the k-level facility location problem. SIAM J Discrete Math, 2004, 18: 207-217

[2] Byrka J, Aardal K I. An optimal bifactor approximation algorithm for the metric uncapacitated facility location problem. SIAM J Comput, 2010, 39: 2212-2213

[3] Chen X, Chen B. Approximation algorithms for soft-capacitated facility location in capacitated network design. Algorithmica, 2009, 53: 263-297

[4] Du D, Lu R, Xu D. A primal-dual approximation algorithm for the facility location problem with submodular penalties. Algorithmica,

[5] Du D, Wang X, Xu D. An approximation algorithm for the k-level capacitated facility location problem. J Comb Optim, 2010, 20: 361-368

[6] Guha S, Khuller S. Greedy strike back: improved facility location algorithms. J Algorithms, 1999, 31: 228-248

[7] Jain K, Mahdian M, Markakis E, Saberi A, Vazirani V V. Greedy facility location algorithms analyzed using dual fitting with factor-revealing LP. J ACM, 2003, 50: 795-824

[8] Jain K, Vazirani V V. Approximation algorithms for metric facility location and k-median problems using the primal-dual schema and Lagrangian relaxation. J ACM, 2001, 48: 274-296

[9] Li S. A 1.488-approximation algorithm for the uncapacitated facility location problem. In: Proceedings of ICALP. 2011, Part II: 77-88

[10] Mahdian M, Ye Y, Zhang J. Approximation algorithms for metric facility location problems. SIAM J Comput, 2006, 36: 411-432

[11] Ravi R, Sinha A. Hedging uncertainty: approximation algorithms for stochastic optimization programs. Math Program, 2006, 108: 97-114

[12] Shmoys D B, Swamy C, Levi R. Facility location with service installation costs. In: Proceedings of SODA. 2004, 1081-1090

[13] Shmoys D B, Tardös E, Aardal K I. Approximation algorithms for facility location problems (extended abstract). In: Proceedings of STOC. 1997, 265-274

[14] Shu J. An efficient greedy heuristic for warehouse-retailer network design optimization. Transport Sci, 2010, 44: 183-192

[15] Shu J, Teo C P, Shen Z J Max. Stochastic transportation-inventory network design problem. Oper Res, 2005, 53: 48-60

[16] Wang Z, Du D, Gabor A F, Xu D. An approximation algorithm for solving the k-level stochastic facility location problem. Oper Res Lett, 2010, 38: 386-389

[17] Wang Z, Du D, Xu D. A primal-dual approximation algorithm for the k-level stochastic facility location problem. In: Proceedings of AAIM. 2010, 253-260

[18] Xu D, Zhang S. Approximation algorithm for facility location problems with service installation costs. Oper Res Lett, 2008, 36: 46-50

[19] Ye Y, Zhang J. An approximation algorithm for the dynamic facility location problem. In: Combinatorial Optimization in Communication Networks. Dordrecht: Kluwer Academic Publishers, 2005, 623-637

[20] Zhang J. Approximating the two-level facility location problem via a quasi-greedy approach. Math Program, 2006, 108: 159-176

[21] Zhang J, Chen B, Ye Y. A multiexchange local search algorithm for the capacitated facility location problem. Math Oper Res, 2005, 30: 389-403

[22] Zhang P. A new approximation algorithm for the k-facility location problem. Theor Comput Sci, 2007, 384: 126-135

RIGHTS & PERMISSIONS

2014 Higher Education Press and Springer-Verlag Berlin Heidelberg