| Article ID | Journal | Published Year | Pages | File Type |
|---|---|---|---|---|
| 429060 | Information Processing Letters | 2011 | 5 Pages |
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.
