Approximating soft-capacitated facility location problem with uncertainty |
| |
Authors: | Shuxin Cai Wenguo Yang Yaohua Tang |
| |
Affiliation: | 1. College of Engineering and Information Technology, Graduate University of Chinese Academy of Sciences, Beijing, 100049, China 2. School of Mathematical Sciences, Graduate University of Chinese Academy of Sciences, Beijing, 100049, China
|
| |
Abstract: | In this paper we devise the stochastic and robust approaches to study the soft-capacitated facility location problem with uncertainty. We first present a new stochastic soft-capacitated model called The 2-Stage Soft Capacitated Facility Location Problem and solve it via an approximation algorithm by reducing it to linear-cost version of 2-stage facility location problem and dynamic facility location problem. We then present a novel robust model of soft-capacitated facility location, The Robust Soft Capacitated Facility Location Problem. To solve it, we improve the approximation algorithm proposed by Byrka et al. (LP-rounding algorithms for facility-location problems. CoRR, 2010a) for RFTFL and then treat it similarly as in the stochastic case. The improvement results in an approximation factor of (alpha + 4) for the robust fault-tolerant facility location problem, which is best so far. |
| |
Keywords: | |
本文献已被 SpringerLink 等数据库收录! |
|