کد مقاله | کد نشریه | سال انتشار | مقاله انگلیسی | نسخه تمام متن |
---|---|---|---|---|
427744 | 686551 | 2012 | 4 صفحه PDF | دانلود رایگان |
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.
Journal: Information Processing Letters - Volume 112, Issue 10, 31 May 2012, Pages 361–364