Approximation Algorithms for the Robust Facility Location Problem with Penalties

DOI10.1007/978-3-319-08377-3_14zbMath1327.90097OpenAlexW2798691779MaRDI QIDQ2942466

Fengmin Wang, Chen-Chen Wu, Da-Chuan Xu

Publication date: 11 September 2015

Published in: Springer Proceedings in Mathematics & Statistics (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1007/978-3-319-08377-3_14

zbMATH Keywords

approximation algorithmfacility location problemgreedy augmentationprimal-dual

Mathematics Subject Classification ID

Integer programming (90C10) Approximation methods and heuristics in mathematical programming (90C59) Discrete location and assignment (90B80)

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Approximation algorithms for soft-capacitated facility location in capacitated network design
• An improved approximation algorithm for uncapacitated facility location problem with penalties
• An LP rounding algorithm for approximating uncapacitated facility location problem with penalties
• A new approximation algorithm for the \(k\)-facility location problem
• A primal-dual approximation algorithm for the facility location problem with submodular penalties
• Approximating the two-level facility location problem via a quasi-greedy approach
• A 1.488 Approximation Algorithm for the Uncapacitated Facility Location Problem
• Greedy facility location algorithms analyzed using dual fitting with factor-revealing LP
• Approximation algorithms for metric facility location and k -Median problems using the primal-dual schema and Lagrangian relaxation
• Greedy Strikes Back: Improved Facility Location Algorithms
• Improved Approximation Algorithms for the Uncapacitated Facility Location Problem
• Improved Combinatorial Approximation Algorithms for the k-Level Facility Location Problem
• Improved Approximation Algorithms for the Facility Location Problems with Linear/submodular Penalty
• Improved Combinatorial Algorithms for Facility Location Problems
• A Multiexchange Local Search Algorithm for the Capacitated Facility Location Problem

This page was built for publication: Approximation Algorithms for the Robust Facility Location Problem with Penalties