收录:
摘要:
We consider the robust alpha fault-tolerant facility location problem (alpha-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 alpha-RFLP (fixed alpha >= 2), the same algorithm with a different subroutine tailored for alpha >= 2 provides an improved approximation ratio 1.005 + 6.015 alpha comparing to 1.5 + 7.5 alpha 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. (C) 2012 Elsevier B.V. All rights reserved.
关键词:
通讯作者信息:
电子邮件地址: