Approximation algorithms for the Fault-Tolerant Facility Placement problem

In the Fault-Tolerant Facility Placement problem (FTFP) we are given a set of customers C, a set of sites F, and distances between customers and sites. We assume that the distances satisfy the triangle inequality. Each customer j has a demand rj and each site may open an unbounded number of facilities. The objective is to minimize the total cost of opening facilities and connecting each customer j to rj different open facilities. We present two LP-rounding algorithms for FTFP. The first algorithm achieves an approximation ratio of 4. The second algorithm uses the method of filtering to improve the ratio to 3.16.