Fault-tolerant facility allocation
Date
2013
Authors
Shen, H.
Xu, S.
Editors
Pardalos, P.
Du, D.
Graham, R.
Du, D.
Graham, R.
Advisors
Journal Title
Journal ISSN
Volume Title
Type:
Book chapter
Citation
Handbook of Combinatorial Optimization, 2013 / Pardalos, P., Du, D., Graham, R. (ed./s), vol.2-5, Ch.27, pp.1293-1309
Statement of Responsibility
Hong Shen and Shihong Xu
Conference Name
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.
School/Discipline
Dissertation Note
Provenance
Description
Access Status
Rights
© Springer Science+Business Media New York 2013