Indexed by:
Abstract:
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.
Keyword:
Reprint Author's Address:
Source :
INFORMATION PROCESSING LETTERS
ISSN: 0020-0190
Year: 2012
Issue: 10
Volume: 112
Page: 361-364
0 . 5 0 0
JCR@2022
ESI Discipline: COMPUTER SCIENCE;
JCR Journal Grade:4
CAS Journal Grade:4
Cited Count:
WoS CC Cited Count: 5
SCOPUS Cited Count: 5
ESI Highly Cited Papers on the List: 0 Unfold All
WanFang Cited Count:
Chinese Cited Count:
30 Days PV: 7
Affiliated Colleges: