Loading...
Please wait, while we are loading the content...
Similar Documents
Fault-tolerant facility location: a randomized dependent LP-rounding algorithm. arXiv:1003.1295v1
| Content Provider | CiteSeerX |
|---|---|
| Author | Srinivasan, Aravind Swamy, Chaitanya Byrka, Jaroslaw |
| Abstract | Abstract. 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. 1 |
| File Format | |
| Access Restriction | Open |
| Subject Keyword | 725-approximation Algorithm Uncapacitated Facility Location Algorithm Benefit Rounding Procedure 076-approximation Algorithm Facility Location Problem Laminar Family Dependent-rounding Technique Randomized Dependent Lp-rounding Algorithm Disjoint Cluster Swamy Shmoys Facility Location Hierarchical Clustering Scheme Dependent-rounding Approach Lp-rounding Approximation Algorithm Important Concept Tight Analysis Uncover New Property Improved Approximation Ratio First Application Fault-tolerant Facility Location Dependent Rounding |
| Content Type | Text |
| Resource Type | Article |
