A DISTRIBUTED APPROXIMATION ALGORITHM FOR FAULT-TOLERANT METRIC FACILITY LOCATION

作者：Xu Shihong^*; Shen Hong

来源：International Journal of Foundations of Computer Science, 2011, 22(5): 1019-1034.

DOI：10.1142/S0129054111008544

• Approximation algorithms
• distributed algorithms
• fault tolerance
• metric facility location problem

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 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 |R| . 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.

• 出版日期2011-8