A primal-dual 3-approximation algorithm for the stochastic facility location problem with submodular penalties

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.

Keywords:

• stochastic facility location
• approximation algorithm
• submodular function

AMS Subject Classifications:

• 90C10
• 90C27
• 68W25

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.