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 r(j) 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 r(j) 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. Published by Elsevier B.V.
approximation algorithms