  We give a new randomized LP-rounding 1.725-approximation algorithm for the
metric Fault-Tolerant Uncapacitated Facility Location problem. This improves on
the previously best known 2.076-approximation algorithm of Swamy & Shmoys. To
the best of our knowledge, our work provides the first application of a
dependent-rounding technique in the domain of facility location. The analysis
of our algorithm benefits from, and extends, methods developed for
Uncapacitated Facility Location; it also helps uncover new properties of the
dependent-rounding approach. An important concept that we develop is a novel,
hierarchical clustering scheme. Typically, LP-rounding approximation algorithms
for facility location problems are based on partitioning facilities into
disjoint clusters and opening at least one facility in each cluster. We extend
this approach and construct a laminar family of clusters, which then guides the
rounding procedure. It allows to exploit properties of dependent rounding, and
provides a quite tight analysis resulting in the improved approximation ratio.
