Improved approximation algorithms for constrained fault-tolerant resource allocation

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 RiRi facilities with opening cost fifi. Each client j   requires an allocation of rjrj open facilities and connecting j to any facility at site i   incurs a connection cost cijcij. The goal is to minimize the total cost of this resource allocation scenario. FTRA   generalizes the Unconstrained Fault-Tolerant Resource Allocation (FTRA∞FTRA∞) [1] and the classical Fault-Tolerant Facility Location (FTFL) [2] problems: for every site i  , FTRA∞FTRA∞ does not have the constraint RiRi, whereas FTFL   sets Ri=1Ri=1. These problems are said to be uniform if all rjrj'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)O(n4) time, where n is the total number of sites and clients.