Abstract
In this paper, we consider the stochastic facility location problem with submodular penalties. By exploring the structural properties of submodular function, we present a primal-dual -approximation algorithm for the problem.
Acknowledgments
We would like to thank two anonymous referees for their insightful and helpful comments on an earlier version of this paper. The first author’s research is supported by NSF of China (No. 11071268), Scientific Research Common Program of Beijing Municipal Commission of Education (No. KM201210005033), and China Scholarship Council.