LP-based approximation algorithms for capacitated facility location

DOI10.1007/s10107-010-0380-8zbMath1247.90055OpenAlexW2028549267MaRDI QIDQ662296

Retsef Levi, David B. Shmoys, Chaitanya Swamy

Publication date: 22 February 2012

Published in: Mathematical Programming. Series A. Series B (Search for Journal in Brave)

Full work available at URL: http://citeseerx.ist.psu.edu/viewdoc/summary?doi=10.1.1.83.1797

zbMATH Keywords

capacitated facility location problemLP-based approximation algorithms

Mathematics Subject Classification ID

Linear programming (90C05) Transportation, logistics and supply chain management (90B06) Combinatorial optimization (90C27) Approximation algorithms (68W25)

Related Items (15)

Combinatorial approximation algorithms for the robust facility location problem with penalties ⋮ 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 ⋮ Capacitated covering problems in geometric spaces ⋮ Capacitated facility location with outliers/penalties ⋮ LP-Based Algorithms for Capacitated Facility Location ⋮ The stochastic capacitated branch restructuring problem ⋮ An LP-rounding based algorithm for a capacitated uniform facility location problem with penalties ⋮ Constant factor approximation algorithm for uniform hard capacitated knapsack median problem ⋮ A Game Theoretic Model for the Optimal Location of Integrated Air Defense System Missile Batteries ⋮ A Branch-and-Price Algorithm for Facility Location with General Facility Cost Functions ⋮ Capacitated Covering Problems in Geometric Spaces

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Capacitated facility location: Separation algorithms and computational experience
• An approximation algorithm for the generalized assignment problem
• Improved approximation algorithms for capacitated facility location problems
• Approximation Algorithms for the Capacitated Multi-Item Lot-Sizing Problem via Flow-Cover Inequalities
• Approximation Algorithms for Metric Facility Location Problems
• Primal-Dual Schema for Capacitated Covering Problems
• Approximation algorithms for metric facility location and k -Median problems using the primal-dual schema and Lagrangian relaxation
• Valid Linear Inequalities for Fixed Charge Problems
• Analysis of a Local Search Heuristic for Facility Location Problems
• A Multiexchange Local Search Algorithm for the Capacitated Facility Location Problem
• Integer Programming and Combinatorial Optimization
• Algorithms - ESA 2003

This page was built for publication: LP-based approximation algorithms for capacitated facility location