TY - GEN

T1 - A distributed (|R|,2)-approximation algorithm for Fault-Tolerant Facility Location

AU - Xu, Shihong

AU - Shen, Hong

PY - 2009

Y1 - 2009

N2 - We propose an approximation algorithm for the problem of Fault-Tolerant Facility Location which is implemented in a distributed and asynchronous manner within O(n) rounds of communication. Here n is the number of vertices in the network. As far as we know, the performance guarantee of similar algorithms (centralized) remains unknown except a special case where all cities have a uniform connectivity requirement. In this paper, we assume the shortest-path routing scheme deployed, as well as a constant (given) size of R, which represents the distinct levels of fault-tolerant capability provided by the system (Le distinct connectivity requirements), and prove that the cost of our solution is no more than \R\ F* + 2 • C* in the general case, where F* and C* are respectively the facility cost and connection cost in an optimal solution. Further more, extensive numerical experiments showed that the quality of our solutions is comparable to the optimal solutions when \R\ is no more than 10.

AB - We propose an approximation algorithm for the problem of Fault-Tolerant Facility Location which is implemented in a distributed and asynchronous manner within O(n) rounds of communication. Here n is the number of vertices in the network. As far as we know, the performance guarantee of similar algorithms (centralized) remains unknown except a special case where all cities have a uniform connectivity requirement. In this paper, we assume the shortest-path routing scheme deployed, as well as a constant (given) size of R, which represents the distinct levels of fault-tolerant capability provided by the system (Le distinct connectivity requirements), and prove that the cost of our solution is no more than \R\ F* + 2 • C* in the general case, where F* and C* are respectively the facility cost and connection cost in an optimal solution. Further more, extensive numerical experiments showed that the quality of our solutions is comparable to the optimal solutions when \R\ is no more than 10.

UR - http://www.scopus.com/inward/record.url?scp=77951013867&partnerID=8YFLogxK

U2 - 10.1109/PDCAT.2009.16

DO - 10.1109/PDCAT.2009.16

M3 - Conference contribution

AN - SCOPUS:77951013867

SN - 9780769539140

T3 - Parallel and Distributed Computing, Applications and Technologies, PDCAT Proceedings

SP - 72

EP - 79

BT - 2009 International Conference on Parallel and Distributed Computing, Applications and Technologies, PDCAT 2009

T2 - 2009 International Conference on Parallel and Distributed Computing, Applications and Technologies, PDCAT 2009

Y2 - 8 December 2009 through 11 December 2009

ER -