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 T, and distances between customers and sites. We assume that the distances satisfy the triangle inequality. Each customer j has a demand r, 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,- 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.