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α⩾2), the same algorithm with a different subroutine tailored for α⩾2α⩾2 provides an improved approximation ratio 1.005+6.015α1.005+6.015α comparing to 1.5+7.5α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.

► Present an improved approximation algorithm with ratio 5.236 for the 1-RFLP. ► Provide an improved approximation ratio 1.005+6.015α1.005+6.015α for the general α  -RFLP (α⩾2α⩾2). ► The key component is the resolution of an auxiliary facility location problem.