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, DOI: 10.1007/s00453-011-9526-1

[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. M. 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. Combinatorial Optimization in Communication Networks, 2005, Dordrecht: Kluwer Academic Publishers 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