Please use this identifier to cite or link to this item:
Scopus Web of Science® Altmetric
Type: Conference paper
Title: A distributed (|R|,2)-approximation algorithm for fault-tolerant facility location
Author: Xu, S.
Shen, H.
Citation: Proceedings: 2009 International Conference on Parallel and Distributed Computing, Applications and Technologies, PDCAT 2009, 8-11 December 2009, Higashi Hiroshima, Japan: pp.72-79
Publisher: IEEE
Publisher Place: USA
Issue Date: 2009
ISBN: 9780769539140
Conference Name: International Conference on Parallel and Distributed Computing, Applications and Technologies (10th : 2009 : Hiroshima, Japan)
Statement of
Shihong Xu and Hong Shen
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* 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 algorithm
facility location
fault tolerance
Rights: Copyright © 2009 by The Institute of Electrical and Electronics Engineers
DOI: 10.1109/PDCAT.2009.16
Published version:
Appears in Collections:Aurora harvest
Computer Science publications

Files in This Item:
There are no files associated with this item.

Items in DSpace are protected by copyright, with all rights reserved, unless otherwise indicated.