## 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_{∞}) [1] and the classical Fault-Tolerant Facility Location (FTFL) [2] 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 [3]. For the uniform FTRA, we provide a 1.52-approximation primal-dual algorithm in O(n4) time, where n is the total number of sites and clients.

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

Pages (from-to) | 118-128 |

Number of pages | 11 |

Journal | Theoretical Computer Science |

Volume | 590 |

DOIs | |

Publication status | Published - 26 Jul 2015 |

Externally published | Yes |

## Keywords

- Approximation algorithms
- LP-rounding
- Primal-dual
- Reduction
- Resource allocation
- Time complexity