Computer Science – Data Structures and Algorithms
Scientific paper
2010-03-05
Computer Science
Data Structures and Algorithms
conference paper + proofs in appendices
Scientific paper
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.
Byrka Jaroslaw
Srinivasan Aravind
Swamy Chaitanya
No associations
LandOfFree
Fault-Tolerant Facility Location: a randomized dependent LP-rounding algorithm does not yet have a rating. At this time, there are no reviews or comments for this scientific paper.
If you have personal experience with Fault-Tolerant Facility Location: a randomized dependent LP-rounding algorithm, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Fault-Tolerant Facility Location: a randomized dependent LP-rounding algorithm will most certainly appreciate the feedback.
Profile ID: LFWR-SCP-O-687933