Dependent Rounding and Fault Tolerant Facility Location

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.

(Joint work with A. Srinivasan and C. Swamy.)

back to EIDMA Seminar Combinatorial Theory announcements