Article ID | Journal | Published Year | Pages | File Type |
---|---|---|---|---|
8051700 | Applied Mathematical Modelling | 2018 | 10 Pages |
Abstract
In this paper, we study the weighted two-stage stochastic fault-tolerant facility location problem. We present a deterministic LP-rounding 5-approximation algorithm by exploiting both of its stochastic and fault-tolerant structures. We further offer an improved randomized LP-rounding 3.8617-approximation algorithm along with the corresponding derandomized version with the same approximation ratio.
Related Topics
Physical Sciences and Engineering
Engineering
Computational Mechanics
Authors
Sai Ji, Dachuan Xu, Donglei Du, Yijing Wang,