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

详细信息    查看全文

• 作者：Yu Li^a ; ^{liyubjut@gmail.com} ; Dachuan Xu^b ; ^{xudc@bjut.edu.cn} ; Donglei Du^c ; ^ddu@unb.ca ; Naihua Xiu^a ; ^{nhxiu@center.njtu.edu.cn}
• 关键词：Facility location ; Approximation algorithm ; Fault tolerance
• 刊名：Information Processing Letters
• 出版年：2012
• 出版时间：31 May, 2012
• 年：2012
• 卷：112
• 期：10
• 页码：361-364
• 全文大小：133 K

文摘

We consider the robust ¦Á fault-tolerant facility location problem (¦Á-RFLP), recently introduced by Chechik and Peleg (2010) . 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 ), the same algorithm with a different subroutine tailored for provides an improved approximation ratio comparing to 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) to estimate the total weighted facility open cost and shipping cost.