The Fault-Tolerant Facility Placement problem (FTFP) is a generalization of the Uncapacitated Facility Location Problem (UFL). In FTFP we are given a set of facility sites and a set of clients. Opening a facility at site i costs f_i and connecting client j to a facility at site i costs d_(ij), where the costs d_(ij) satisfy the triangle inequality. Multiple facilities can be opened at any site. Each client j has a demand r_j, which means that it needs to be connected to r_j different facilities. The goal is to minimize the sum of facility opening cost and connection cost. The main result of this paper is a 1.575-approximation algorithm for FTFP, based on LP-rounding.
展开▼
