Please use this identifier to cite or link to this item:
Scopus Web of Science® Altmetric
Type: Book chapter
Title: Fault-tolerant facility allocation
Author: Shen, H.
Xu, S.
Citation: Handbook of Combinatorial Optimization, 2nd edn, 2013 / Pardalos, P., Du, D., Graham, R. (ed./s), Ch.27, pp.1293-1309
Publisher: Springer
Publisher Place: New York
Issue Date: 2013
ISBN: 1441979964
Statement of
Hong Shen and Shihong Xu
Abstract: The problem of Fault-Tolerant Facility Allocation (FTFA) is a relaxation of the classical Fault-Tolerant Facility Location (FTFL) problem (Jain K, Vazirani VV (2000) An approximation algorithm for the fault tolerant metric facility location problem. In: APPROX ’00: proceedings of the third international workshop on approximation algorithms for combinatorial optimization, London, UK. Springer, pp 177–183).Given a set of sites, each containing a set of identical facilities and associated with an operating cost for each facility, a set of clients, where each client-site pair has a (distance-based) connection cost and each client has a connection requirement FTFA, requires to compute a connection scheme between clients and sites such that each client is allocated a desired number of facilities and the total combined facility (operating) cost and connection cost for all clients to access their required facilities is minimum. Compared with the FTFL problem which restricts that at most one facility can be opened at each site, the FTFA problem is less constrained and hence incurs a smaller cost. This chapter introduces our recent work on this problem (Xu S, Shen H (2009) The fault-tolerant facility allocation problem. In ISAAC, pp 689–698) and shows that the metric version of FTFA, i.e., the connection costs satisfy triangle inequality, is solvable in polynomial time within approximation ratio 1.861, which is better than the best approximation ratio 2.076 for metric FTFL (Swamy C, Shmoys DB (2008) Fault-tolerant facility location. ACMTrans Algorithms 4(4):1–27) known that time.
Rights: © Springer Science+Business Media New York 2013
RMID: 0030075150
DOI: 10.1007/978-1-4419-7997-1_11
Published version:
Appears in Collections: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.