Please use this identifier to cite or link to this item: http://hdl.handle.net/2440/70161
Citations
Scopus Web of ScienceĀ® Altmetric
?
?
Type: Journal article
Title: A distributed approximation algorithm for fault-tolerant metric facility location
Author: Xu, S.
Shen, H.
Citation: International Journal of Foundations of Computer Science, 2011; 22(5):1019-1034
Publisher: World Scientific Publishing Co. Pte. Ltd.
Issue Date: 2011
ISSN: 0129-0541
1793-6373
Statement of
Responsibility: 
Shihong Xu and Hong Shen
Abstract: In this paper, we propose an approximation algorithm for the Fault-Tolerant Metric Facility Location problem which can be implemented in a distributed and asynchronous manner within O(n) rounds of communication, where n is the number of vertices in the network. Given a constant size set $\mathcal{R}$ which represents distinct levels of fault-tolerant requirements of all cities, as well as the two-part (facility and connection) cost of the optimal solution, i.e. F* + C*, the cost of our solution is no more than $|\mathcal{R}|\, \cdot \,F^* \, + \,2C^* $ for the general case, and less than F* + 2C* for the special case where all cities have a uniform connectivity requirement. Extensive numerical experiments showed that the quality of our solutions is comparable (within 4% error) to the optimal solution in practice.
Keywords: Approximation algorithms; distributed algorithms; fault tolerance; metric facility location problem
Rights: Copyright of International Journal of Foundations of Computer Science is the property of World Scientific Publishing Company
RMID: 0020112315
DOI: 10.1142/S0129054111008544
Grant ID: http://purl.org/au-research/grants/arc/DP0985063
Published version: http://proxy.library.adelaide.edu.au/login?url=http://search.ebscohost.com/login.aspx?direct=true&db=aph&AN=64171691&site=ehost-live&scope=site
Appears in Collections: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.