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: this allows us to exploit properties of dependent rounding, and provides a quite tight analysis resulting in the improved approximation ratio.
This work was partially supported by: (i) the Future and Emerging Technologies Unit of EC (IST priority - 6th FP), under contract no. FP6-021235-2 (project ARRIVAL), (ii) MNISW grant number N N206 1723 33, 2007–2010, (iii) NSF ITR Award CNS-0426683 and NSF Award CNS-0626636, and (iv) NSERC grant 327620-09 and an Ontario Early Researcher Award.
This is a preview of subscription content, log in via an institution to check access.
Access this chapter
Tax calculation will be finalised at checkout
Purchases are for personal use only
Preview
Unable to display preview. Download preview PDF.
Similar content being viewed by others
References
Ageev, A., Sviridenko, M.: Pipage rounding: a new method of constructing algorithms with proven performance guarantee. Journal of Combinatorial Optimization 8(3), 307–328 (2004)
Byrka, J.: An optimal bifactor approximation algorithm for the metric uncapacitated facility location problem. In: APPROX-RANDOM, pp. 29–43 (2007)
Byrka, J., Srinivasan, A., Swamy, C.: Fault-tolerant facility location: a randomized dependent LP-rounding algorithm. arXiv:1003.1295v1
Chudak, F.A., Shmoys, D.B.: Improved approximation algorithms for the uncapacitated facility location problem. SIAM J. Comput. 33(1), 1–25 (2003)
Guha, S., Khuller, S.: Greedy strikes back: Improved facility location algorithms. J. Algorithms 31(1), 228–248 (1999)
Guha, S., Meyerson, A., Munagala, K.: A constant factor approximation algorithm for the fault-tolerant facility location problem. J. Algorithms 48(2), 429–440 (2003)
Jain, K., Vazirani, V.V.: An approximation algorithm for the fault tolerant metric facility location problem. Algorithmica 38(3), 433–439 (2003)
Lin, J.-H., Vitter, J.S.: Epsilon-approximations with minimum packing constraint violation (extended abstract). In: STOC, pp. 771–782 (1992)
Shmoys, D.B., Tardos, É., Aardal, K.: Approximation algorithms for facility location problems (extended abstract). In: STOC, pp. 265–274 (1997)
Srinivasan, A.: Distributions on level-sets with applications to approximation algorithms. In: FOCS, pp. 588–597 (2001)
Swamy, C., Shmoys, D.B.: Fault-tolerant facility location. ACM Transactions on Algorithms 4(4) (2008)
Author information
Authors and Affiliations
Editor information
Editors and Affiliations
Rights and permissions
Copyright information
© 2010 Springer-Verlag Berlin Heidelberg
About this paper
Cite this paper
Byrka, J., Srinivasan, A., Swamy, C. (2010). Fault-Tolerant Facility Location: A Randomized Dependent LP-Rounding Algorithm. In: Eisenbrand, F., Shepherd, F.B. (eds) Integer Programming and Combinatorial Optimization. IPCO 2010. Lecture Notes in Computer Science, vol 6080. Springer, Berlin, Heidelberg. https://doi.org/10.1007/978-3-642-13036-6_19
Download citation
DOI: https://doi.org/10.1007/978-3-642-13036-6_19
Publisher Name: Springer, Berlin, Heidelberg
Print ISBN: 978-3-642-13035-9
Online ISBN: 978-3-642-13036-6
eBook Packages: Computer ScienceComputer Science (R0)