Please use this identifier to cite or link to this item:
https://hdl.handle.net/2440/59020
Citations | ||
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 Responsibility: | 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: | http://dx.doi.org/10.1109/pdcat.2009.16 |
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.