Approximation algorithms for the Fault-Tolerant Facility Placement problem

In the Fault-Tolerant Facility Placement   problem (FTFP) we are given a set of customers CC, a set of sites FF, and distances between customers and sites. We assume that the distances satisfy the triangle inequality. Each customer j   has a demand rjrj 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 rjrj 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.

► We studied a generalized version of Facility Location (FL) problem.
► We use LP-rounding technique similar to that used for the standard FL problem.
► Our algorithm is the first polynomial time algorithm for this problem.
► The main novelty is on bounding facility cost.