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

DOI10.1007/978-3-642-13036-6_19zbMATH Open1281.90021arXiv1003.1295OpenAlexW3100218344MaRDI 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)

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.

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

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

Mathematics Subject Classification ID

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

Cited In (17)

• 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
• Improved Approximation Algorithm for Fault-Tolerant Facility Placement
• 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
• 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
• LP-Based Algorithms for Capacitated 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)