The fault-tolerant facility allocation problem

Shihong Xu, Hong Shen

Research output: Chapter in Book/Report/Conference proceedingConference contributionpeer-review

19 Citations (Scopus)


We study the problem of Fault-Tolerant Facility Allocation (FTFA) which is a relaxation of the classical Fault-Tolerant Facility Location (FTFL) problem [1]. Given a set of sites, a set of cities, and corresponding facility operating cost at each site as well as connection cost for each site-city pair, FTFA requires to allocate each site a proper number of facilities and further each city a prespecified number of facilities to access. The objective is to find such an allocation that minimizes the total combined cost for facility operating and service accessing. In comparison with the FTFL problem which restricts each site to at most one facility, the FTFA problem is less constrained and therefore incurs less cost which is desirable in application. In this paper, we consider the metric FTFA problem where the given connection costs satisfy triangle inequality and we present a polynomial-time algorithm with approximation factor 1.861 which is better than the best known approximation factor 2.076 for the metric FTFL problem [2].

Original languageEnglish
Title of host publicationAlgorithms and Computation - 20th International Symposium, ISAAC 2009, Proceedings
Number of pages10
Publication statusPublished - 2009
Externally publishedYes
Event20th International Symposium on Algorithms and Computation, ISAAC 2009 - Honolulu, HI, United States
Duration: 16 Dec 200918 Dec 2009

Publication series

NameLecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)
Volume5878 LNCS
ISSN (Print)0302-9743
ISSN (Electronic)1611-3349


Conference20th International Symposium on Algorithms and Computation, ISAAC 2009
Country/TerritoryUnited States
CityHonolulu, HI


Dive into the research topics of 'The fault-tolerant facility allocation problem'. Together they form a unique fingerprint.

Cite this