  The Fault-Tolerant Facility Placement problem (FTFP) is a generalization of
the classic 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}$.
We assume that the connection costs (distances) $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 (some of which could be located on the same site). 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. The algorithm first reduces the demands to values
polynomial in the number of sites. Then it uses a technique that we call
adaptive partitioning, which partitions the instance by splitting clients into
unit demands and creating a number of (not yet opened) facilities at each site.
It also partitions the optimal fractional solution to produce a fractional
solution for this new instance. The partitioned instance satisfies a number of
properties that allow us to exploit existing LP-rounding methods for UFL to
round our partitioned solution to an integral solution, preserving the
approximation ratio. In particular, our 1.575-approximation algorithm is based
on the ideas from the 1.575-approximation algorithm for UFL by Byrka et al.,
with changes necessary to satisfy the fault-tolerance requirement.
