Please use this identifier to cite or link to this item:
Scopus Web of Science® Altmetric
Type: Conference paper
Title: The fault-tolerant facility allocation problem
Author: Xu, S.
Shen, H.
Citation: Lecture Notes in Artificial Intelligence, 2009 / Dong, Y., Du, D.Z., Ibarra, O. (ed./s), vol.5878 LNCS, pp.689-698
Publisher: Springer-Verlag Berlin
Publisher Place: Heidelberger Platz 3 Berlin Germany D-14197
Issue Date: 2009
Series/Report no.: Lecture Notes in Computer Science
ISBN: 3642106307
ISSN: 0302-9743
Conference Name: International Symposium on Algorithms and Computation (ISAAC) (16 Dec 2009 - 18 Dec 2009 : Honolulu, HI, USA)
Editor: Dong, Y.
Du, D.Z.
Ibarra, O.
Statement of
Shihong Xu and Hong Shen
Abstract: 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].
Rights: © Springer-Verlag Berlin Heidelberg 2009
DOI: 10.1007/978-3-642-10631-6_70
Published version:
Appears in Collections:Aurora harvest
Computer Science publications

Files in This Item:
There are no files associated with this item.

Items in DSpace are protected by copyright, with all rights reserved, unless otherwise indicated.