  We studied the Fault-Tolerant Facility Placement problem (FTFP) which
generalizes the uncapacitated facility location problem (UFL). In FTFP, we are
given a set F of sites at which facilities can be built, and a set C of clients
with some demands that need to be satisfied by different facilities. A client
$j$ has demand $r_j$. Building one facility at a site $i$ incurs a cost $f_i$,
and connecting one unit of demand from client $j$ to a facility at site
$i\in\fac$ costs $d_{ij}$. $d_{ij}$'s are assumed to form a metric. A feasible
solution specifies the number of facilities to be built at each site and the
way to connect demands from clients to facilities, with the restriction that
demands from the same client must go to different facilities. Facilities at the
same site are considered different. The goal is to find a solution with minimum
total cost. We gave a 1.7245-approximation algorithm to the FTFP problem. Our
technique is via a reduction to the Fault-Tolerant Facility Location problem,
in which each client has demand $r_j$ but each site can have at most one
facility built.
