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 Ri R i facilities with opening cost fi f i . Each client j  requires an allocation of rj r j open facilities and connecting j to any facility at site i  incurs a connection cost cij c i j . 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 Ri R i , whereas FTFL  sets Ri=1 R i = 1 . These problems are said to be uniform if all rj 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 primaldual algorithm in O(n4) O ( n 4 ) time, where n is the total number of sites and clients.
approximation algorithms resource allocation lp-rounding primaldual reduction time complexity