LP-based approximation algorithms for capacitated facility location
From MaRDI portal
In this paper, the authors describe an LP-based approximation algorithms in the case of the capacitated facility location problem with hard capacities. The novel described approximation algorithms, 5-approximation algorithm, is the first LP-based approximation algorithm for the capacitated facility location problem with hard capacities. The algorithm is obtained for the special case in which all of the facility costs are equal, by rounding the optimal solution to the standard LP relaxation. The main idea was to view the optimal primal solution as a bipartite graph and then this was used to construct a partition of the demand and facilities into clusters: each cluster is centered at a client, and the neighbors of this client contained in the cluster are opened (in the fractional solution) in total at least 1/2.
Recommendations
- Integer Programming and Combinatorial Optimization
- LP-based algorithms for capacitated facility location
- LP-based approximation for uniform capacitated facility location problem
- Approximation, Randomization, and Combinatorial Optimization.. Algorithms and Techniques
- Approximation algorithms for hard capacitated \(k\)-facility location problems
Cites work
- A Multiexchange Local Search Algorithm for the Capacitated Facility Location Problem
- Algorithms - ESA 2003
- An approximation algorithm for the generalized assignment problem
- Analysis of a Local Search Heuristic for Facility Location Problems
- Approximation algorithms for metric facility location and k -Median problems using the primal-dual schema and Lagrangian relaxation
- Approximation Algorithms for Metric Facility Location Problems
- Approximation algorithms for the capacitated multi-item lot-sizing problem via flow-cover inequalities
- Capacitated facility location: Separation algorithms and computational experience
- scientific article; zbMATH DE number 1670526 (Why is no real title available?)
- scientific article; zbMATH DE number 2079405 (Why is no real title available?)
- scientific article; zbMATH DE number 1559542 (Why is no real title available?)
- scientific article; zbMATH DE number 1445293 (Why is no real title available?)
- Improved approximation algorithms for capacitated facility location problems
- Integer Programming and Combinatorial Optimization
- Primal-Dual Schema for Capacitated Covering Problems
- Valid Linear Inequalities for Fixed Charge Problems
Cited in
(33)- Approximation of the competitive facility location problem with MIPs
- An LP-rounding based algorithm for a uniform capacitated facility location problem with penalties
- An LP-rounding based algorithm for a capacitated uniform facility location problem with penalties
- 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
- Capacitated covering problems in geometric spaces
- Approximation algorithms for hard capacitated \(k\)-facility location problems
- Combinatorial approximation algorithms for the robust facility location problem with penalties
- A game theoretic model for the optimal location of integrated air defense system missile batteries
- A 5-approximation for capacitated facility location
- LP-based algorithms for capacitated facility location
- Sherali-Adams gaps, flow-cover inequalities and generalized configurations for capacity-constrained facility location
- Integrality gaps for strengthened linear relaxations of capacitated facility location
- Lower Bounds for the Capacitated Facility Location Problem Based on Column Generation
- The Capacitated p-facility Location Problem on the Real Line
- Assignment problem in content distribution networks, unsplittable hard-capacitated facility location
- Assignment problem in content distribution networks: unsplittable hard-capacitated facility location
- A branch-and-price algorithm for facility location with general facility cost functions
- Constant factor approximation algorithm for uniform hard capacitated knapsack median problem
- Capacitated covering problems in geometric spaces
- The stochastic capacitated branch restructuring problem
- Integer Programming and Combinatorial Optimization
- Capacitated facility location with outliers/penalties
- Respecting lower bounds in uniform lower and upper bounded facility location problem
- An LP-rounding based algorithm for soft capacitated facility location problem with submodular penalties
- Uniform capacitated facility location with outliers/penalties
- Capacitated facility location with outliers and uniform facility costs
- An LP-rounding based algorithm for soft capacitated facility location problem with submodular penalties
- Capacitated facility location with outliers and uniform facility costs
- An LP-rounding based algorithm for hard capacitated uniform facility location problem with soft penalties
- Approximation scheme for the single-client capacitated facility location problem with operational cost budget constraint
- The \(p/q\)-\texttt{ACTIVE} uncapacitated facility location problem: investigation of the solution space and an LP-fitting heuristic
This page was built for publication: LP-based approximation algorithms for capacitated facility location
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q662296)
