Please use this identifier to cite or link to this item:
https://hdl.handle.net/2440/109406
Citations | ||
Scopus | Web of Science® | Altmetric |
---|---|---|
?
|
?
|
Type: | Book chapter |
Title: | Fault-tolerant facility allocation |
Author: | Shen, H. Xu, S. |
Citation: | Handbook of Combinatorial Optimization, 2013 / Pardalos, P., Du, D., Graham, R. (ed./s), vol.2-5, Ch.27, pp.1293-1309 |
Publisher: | Springer |
Publisher Place: | New York |
Issue Date: | 2013 |
ISBN: | 1441979964 9781441979964 |
Editor: | Pardalos, P. Du, D. Graham, R. |
Statement of Responsibility: | 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 |
DOI: | 10.1007/978-1-4419-7997-1_11 |
Published version: | http://www.springer.com/gp/book/9781441979964 |
Appears in Collections: | Aurora harvest 3 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.