Jarek Byrka
We give a new LP-rounding 1.724-approximation algorithm for the metric Fault Tolerant Uncapacitated Facility Location problem. This improves on the previously best known 2.076-approximation algorithm of Swamy and Shmoys. Our work presents the first application of the dependent rounding technique in the domain of facility location. As a result the analysis of our algorithm may use methods developed for the standard Uncapacitated Facility Location.
|