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

作者：Xu Dachuan^*; Gao Dongxiao; Wu Chenchen

来源：Optimization, 2015, 64(3): 617-626.

DOI：10.1080/02331934.2013.793326

• 90C27
• 90C10
• 68W25
• approximation algorithm
• stochastic facility location
• submodular function

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.

• 出版日期2015-3-4
• 单位北京工业大学