Back to Search
Start Over
A DISTRIBUTED APPROXIMATION ALGORITHM FOR FAULT-TOLERANT METRIC FACILITY LOCATION.
- Source :
-
International Journal of Foundations of Computer Science . Aug2011, Vol. 22 Issue 5, p1019-1034. 16p. - Publication Year :
- 2011
-
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. [ABSTRACT FROM AUTHOR]
Details
- Language :
- English
- ISSN :
- 01290541
- Volume :
- 22
- Issue :
- 5
- Database :
- Academic Search Index
- Journal :
- International Journal of Foundations of Computer Science
- Publication Type :
- Academic Journal
- Accession number :
- 64171691
- Full Text :
- https://doi.org/10.1142/S0129054111008544