A distributed approximation algorithm for fault-tolerant metric facility location

Shihong Xu, Hong Shen

Research output: Contribution to journalArticlepeer-review

1 Citation (Scopus)


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.

Original languageEnglish
Pages (from-to)1019-1034
Number of pages16
JournalInternational Journal of Foundations of Computer Science
Issue number5
Publication statusPublished - Aug 2011
Externally publishedYes


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


Dive into the research topics of 'A distributed approximation algorithm for fault-tolerant metric facility location'. Together they form a unique fingerprint.

Cite this