A per-scenario bound for the two-stage stochastic facility location problem with linear penalty

Abstract

In this paper, we consider the two-stage stochastic facility location problem with linear penalty. We develop an LP rounding algorithm with the first per-scenario constant approximation bound for this problem.

Keywords:

• facility location problem
• approximation algorithm
• LP rounding
• per-scenario bound

AMS Subject Classifications:

• 68W25
• 90C27

Acknowledgments

The authors would like to thank two anonymous referees for many helpful suggestions.

Notes

The research of the first author is supported by NSF of China [grant number 11071268]. The second author’s research is supported by the Natural Sciences and Engineering Research Council of Canada (NSERC) [grant number 283106]. The third author’s research is supported by NSF of China [grant number 11371001], Scientific Research Common Programme of Beijing Municipal Commission of Education [grant number KM201210005033] and China Scholarship Council.