Please use this identifier to cite or link to this item:
http://hdl.handle.net/2440/109406
Citations  
Scopus  Web of Science®  Altmetric 

?

?

Type:  Book chapter 
Title:  Faulttolerant 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.12931309 
Publisher:  Springer 
Publisher Place:  New York 
Issue Date:  2013 
ISBN:  1441979964 9781441979964 
Statement of Responsibility:  Hong Shen and Shihong Xu 
Abstract:  The problem of FaultTolerant Facility Allocation (FTFA) is a relaxation of the classical FaultTolerant 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 clientsite pair has a (distancebased) 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 faulttolerant 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) Faulttolerant facility location. ACMTrans Algorithms 4(4):1–27) known that time. 
Rights:  © Springer Science+Business Media New York 2013 
RMID:  0030075150 
DOI:  10.1007/9781441979971_11 
Published version:  http://www.springer.com/gp/book/9781441979964 
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.