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

作者：Wu, Chenchen; Du, Donglei; Xu, Dachuan^*

来源：Optimization, 2014, 63(6): 921-930.

DOI：10.1080/02331934.2013.840626

• facility location problem
• approximation algorithm
• LP rounding
• per-scenario bound
• 68W25
• 90C27

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.

• 出版日期2014-6-3
• 单位南开大学; 北京工业大学