TY - GEN

T1 - The fault-tolerant facility allocation problem

AU - Xu, Shihong

AU - Shen, Hong

PY - 2009

Y1 - 2009

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

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

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

U2 - 10.1007/978-3-642-10631-6_70

DO - 10.1007/978-3-642-10631-6_70

M3 - Conference contribution

AN - SCOPUS:75649127295

SN - 3642106307

SN - 9783642106309

T3 - Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)

SP - 689

EP - 698

BT - Algorithms and Computation - 20th International Symposium, ISAAC 2009, Proceedings

T2 - 20th International Symposium on Algorithms and Computation, ISAAC 2009

Y2 - 16 December 2009 through 18 December 2009

ER -