DocumentCode :
2963431
Title :
A Distributed (Constant of R, 2)-Approximation Algorithm for Fault-Tolerant Facility Location
Author :
Xu, Shihong ; Shen, Hong
Author_Institution :
Univ. of Adelaide, Adelaide, SA, Australia
fYear :
2009
fDate :
8-11 Dec. 2009
Firstpage :
72
Lastpage :
79
Abstract :
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 (i. e 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.
Keywords :
approximation theory; computational complexity; distributed algorithms; facility location; fault tolerance; graph theory; connection cost; distributed approximation algorithm; facility cost; fault-tolerant facility location; shortest-path routing; Approximation algorithms; Cities and towns; Cost function; Distributed algorithms; Distributed computing; Fault tolerance; Fault tolerant systems; Industrial plants; Operations research; Routing; approximation algorithm; facility location; fault tolerance;
fLanguage :
English
Publisher :
ieee
Conference_Titel :
Parallel and Distributed Computing, Applications and Technologies, 2009 International Conference on
Conference_Location :
Higashi Hiroshima
Print_ISBN :
978-0-7695-3914-0
Type :
conf
DOI :
10.1109/PDCAT.2009.16
Filename :
5372818
Link To Document :
بازگشت