Fault-tolerant facility location: a randomized dependent LP-rounding algorithm

DOI10.1007/978-3-642-13036-6_19zbMATH Open1281.90021OpenAlexW3100218344MaRDI QIDQ3569822FDOQ3569822

Authors Jaroslaw Byrka, Aravind Srinivasan, Chaitanya Swamy 

Publication date 22 June 2010

Published in Integer Programming and Combinatorial Optimization (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/1003.1295

Mathematics Subject Classification ID

Numerical mathematical programming methods (65K05) Combinatorial optimization (90C27) Stochastic programming (90C15) Integer programming (90C10) Discrete location and assignment (90B80)

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.

Recommendations

• LP-rounding approximation algorithms for two-stage stochastic fault-tolerant facility location problem
• LP-rounding algorithms for the fault-tolerant facility placement problem
• Fault-tolerant facility location
• Improved algorithms for fault tolerant facility location
• A constant factor approximation algorithm for the fault-tolerant facility location problem

Cited In (17)

• Improved approximation algorithm for fault-tolerant facility placement
• Approximation algorithms for the fault-tolerant facility placement problem
• Fault-tolerant concave facility location problem with uniform requirements
• Combinatorial approximation algorithms for the robust facility location problem with penalties
• Improved approximation algorithms for the robust fault-tolerant facility location problem
• Accelerating Benders decomposition with heuristic master problem solutions
• Improved approximation algorithms for constrained fault-tolerant resource allocation
• Approximating soft-capacitated facility location problem with uncertainty
• An approximation algorithm for the stochastic fault-tolerant facility location problem
• Constant approximation for fault-tolerant median problems via iterative rounding
• LP-rounding approximation algorithms for two-stage stochastic fault-tolerant facility location problem
• Approximation algorithms for the fault-tolerant facility location problem with penalties
• LP-based algorithms for capacitated facility location
• Fault-tolerant covering problems in metric spaces
• LP-rounding algorithms for the fault-tolerant facility placement problem
• Approximation algorithms for the fault-tolerant facility location problem with submodular penalties
• Robust fault tolerant uncapacitated facility location

This page was built for publication: Fault-tolerant facility location: a randomized dependent LP-rounding algorithm

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q3569822)