Improved approximation algorithms for the robust fault-tolerant facility location problem

摘要

We consider the robust α fault-tolerant facility location problem (α-RFLP), recently introduced by Chechik and Peleg (2010) [6]. We present an improved approximation algorithm with ratio 5.236 for the 1-RFLP comparing to 6.5 by Chechik and Peleg's. For the general α-RFLP (fixed α≥2), the same algorithm with a different subroutine tailored for α≥2 provides an improved approximation ratio 1.005+ 6.015a comparing to 1.5 + 7.5α by Chechik and Peleg's. The key component of our algorithm is the resolution of an auxiliary facility location problem (FLP) by a variant of the LP-rounding technique of Byrka and Aardal (2010) [2] to estimate the total weighted facility open cost and shipping cost.