TY - JOUR

T1 - A distributed approximation algorithm for fault-tolerant metric facility location

AU - Xu, Shihong

AU - Shen, Hong

N1 - Funding Information:
This work was partially supported by Australian Research Council Discovery Project grant #DP0985063 and ECMS Research Group of Networks, Parallel and Distributed Systems, University of Adelaide.

PY - 2011/8

Y1 - 2011/8

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

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

KW - Approximation algorithms

KW - distributed algorithms

KW - fault tolerance

KW - metric facility location problem

UR - http://www.scopus.com/inward/record.url?scp=80051699356&partnerID=8YFLogxK

U2 - 10.1142/S0129054111008544

DO - 10.1142/S0129054111008544

M3 - Article

AN - SCOPUS:80051699356

SN - 0129-0541

VL - 22

SP - 1019

EP - 1034

JO - International Journal of Foundations of Computer Science

JF - International Journal of Foundations of Computer Science

IS - 5

ER -