A 5-Approximation for Capacitated Facility Location

DOI10.1007/978-3-642-33090-2_13zbMath1365.90159OpenAlexW58289331MaRDI QIDQ2912835

Naveen Garg, Manisha Bansal, Neelima Gupta

Publication date: 25 September 2012

Published in: Algorithms – ESA 2012 (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1007/978-3-642-33090-2_13

Mathematics Subject Classification ID

Approximation methods and heuristics in mathematical programming (90C59) Discrete location and assignment (90B80) Approximation algorithms (68W25)

Related Items (25)

New approximation algorithms for the unsplittable capacitated facility location problem ⋮ Approximation algorithms for hard capacitated \(k\)-facility location problems ⋮ Integrality gaps for strengthened linear relaxations of capacitated facility location ⋮ Bifactor approximation for location routing with vehicle and facility capacities ⋮ LP-based approximation for uniform capacitated facility location problem ⋮ A note on LP-based approximation algorithms for capacitated facility location problem ⋮ Approximation Algorithms for the Capacitated Min–Max Correlation Clustering Problem ⋮ Centrality of trees for capacitated \(k\)-center ⋮ Improved bounds for metric capacitated covering problems ⋮ Constant-factor approximation algorithms for parity-constrained facility location and \(k\)-center ⋮ Unnamed Item ⋮ \(\mathrm{M}^p\)UFLP: universal facility location problem in the \(p\)-th power of metric space ⋮ Unnamed Item ⋮ Capacitated facility location with outliers/penalties ⋮ LP-Based Algorithms for Capacitated Facility Location ⋮ Respecting lower bounds in uniform lower and upper bounded facility location problem ⋮ Unnamed Item ⋮ Iterative partial rounding for vertex cover with hard capacities ⋮ On the cost of essentially fair clusterings ⋮ Easy capacitated facility location problems, with connections to lot-sizing ⋮ Unnamed Item ⋮ Approximation algorithms for the transportation problem with market choice and related models ⋮ Recent Developments in Approximation Algorithms for Facility Location and Clustering Problems ⋮ Constant factor approximation algorithm for uniform hard capacitated knapsack median problem ⋮ Improved local search for universal facility location

This page was built for publication: A 5-Approximation for Capacitated Facility Location