### Abstract

In Constrained Fault-Tolerant Resource Allocation (FTRA) problem, we are given a set of sites containing facilities as resources and a set of clients accessing these resources. Each site i can open at most R_{i} facilities with opening cost f_{i}. Each client j requires an allocation of r _{j} open facilities and connecting j to any facility at site i incurs a connection cost c_{ij}. The goal is to minimize the total cost of this resource allocation scenario. FTRA generalizes the Unconstrained Fault-Tolerant Resource Allocation (FTRA_{∞}) [10] and the classical Fault-Tolerant Facility Location (FTFL) [7] problems: for every site i, FTRA_{∞} does not have the constraint R_{i} , whereas FTFL sets R_{i} = 1. These problems are said to be uniform if all r _{j} 's are the same, and general otherwise. For the general metric FTRA, we first give an LP-rounding algorithm achieving an approximation ratio of 4. Then we show the problem reduces to FTFL, implying the ratio of 1.7245 from [2]. For the uniform FTRA, we provide a 1.52-approximation primal-dual algorithm in O(n^{4}) time, where n is the total number of sites and clients.

Original language | English |
---|---|

Title of host publication | Fundamentals of Computation Theory - 19th International Symposium, FCT 2013, Proceedings |

Editors | Leszek Gąsieniec, Frank Wolter |

Publisher | Springer-Verlag London Ltd. |

Pages | 236-247 |

Number of pages | 12 |

Volume | 8070 |

ISBN (Electronic) | 9783642401640 |

ISBN (Print) | 9783642401633 |

DOIs | |

Publication status | Published - 3 Sep 2013 |

Externally published | Yes |

Event | 19th International Symposium on Fundamentals of Computation Theory, FCT 2013 - Liverpool, United Kingdom Duration: 19 Aug 2013 → 21 Aug 2013 |

### Publication series

Name | Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics) |
---|---|

Volume | 8070 LNCS |

ISSN (Print) | 0302-9743 |

ISSN (Electronic) | 1611-3349 |

### Conference

Conference | 19th International Symposium on Fundamentals of Computation Theory, FCT 2013 |
---|---|

Country | United Kingdom |

City | Liverpool |

Period | 19/08/13 → 21/08/13 |

## Fingerprint Dive into the research topics of 'Improved approximation algorithms for constrained fault-tolerant resource allocation (Extended abstract)'. Together they form a unique fingerprint.

## Cite this

*Fundamentals of Computation Theory - 19th International Symposium, FCT 2013, Proceedings*(Vol. 8070, pp. 236-247). (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics); Vol. 8070 LNCS). Springer-Verlag London Ltd.. https://doi.org/10.1007/978-3-642-40164-0_23