LP-Based Algorithms for Capacitated Facility Location
From MaRDI portal
Publication:2968155
DOI10.1137/151002320zbMath1359.68298arXiv1407.3263OpenAlexW2593080689MaRDI QIDQ2968155
Mohit Singh, Ola Svensson, Hyung-Chan An
Publication date: 10 March 2017
Published in: SIAM Journal on Computing (Search for Journal in Brave)
Full work available at URL: https://arxiv.org/abs/1407.3263
Linear programming (90C05) Approximation methods and heuristics in mathematical programming (90C59) Discrete location and assignment (90B80) Approximation algorithms (68W25)
Related Items (37)
A Technique for Obtaining True Approximations for k-Center with Covering Constraints ⋮ Integrality gaps for strengthened linear relaxations of capacitated facility location ⋮ Tight approximation for partial vertex cover with hard capacities ⋮ A Water-Filling Primal-Dual Algorithm for Approximating NonLinear Covering Problems ⋮ An Approximation Algorithm for Uniform Capacitated k-Median Problem with $$1+\epsilon $$ Capacity Violation ⋮ A $$(5.83+\epsilon )$$ ( 5.83 + ϵ ) -Approximation Algorithm for Universal Facility Location Problem with Linear 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 ⋮ On inequalities with bounded coefficients and pitch for the min knapsack polytope ⋮ Capacitated covering problems in geometric spaces ⋮ Approximation algorithm for squared metric facility location problem with nonuniform capacities ⋮ Improved bounds for metric capacitated covering problems ⋮ Constant-factor approximation algorithms for parity-constrained facility location and \(k\)-center ⋮ Approximation algorithms for the fault-tolerant facility location problem with submodular penalties ⋮ The facility location problem with maximum distance constraint ⋮ 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 ⋮ Unnamed Item ⋮ 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 ⋮ Local search algorithm for universal facility location problem with linear penalties ⋮ Approximation algorithms for the transportation problem with market choice and related models ⋮ Heuristics for the dynamic facility location problem with modular capacities ⋮ Recent Developments in Approximation Algorithms for Facility Location and Clustering Problems ⋮ Robust \(k\)-center with two types of radii ⋮ An LP-rounding based algorithm for a capacitated uniform facility location problem with penalties ⋮ Robust \(k\)-center with two types of radii ⋮ Generalized Center Problems with Outliers ⋮ Unnamed Item ⋮ An approximation algorithm for stochastic multi-level facility location problem with soft capacities ⋮ Capacitated Covering Problems in Geometric Spaces ⋮ A technique for obtaining true approximations for \(k\)-center with covering constraints
Cites Work
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- A 3-approximation algorithm for the facility location problem with uniform capacities
- LP-based approximation algorithms for capacitated facility location
- The ellipsoid method and its consequences in combinatorial optimization
- Approximation algorithms for geometric median problems
- Improved approximation algorithms for capacitated facility location problems
- Combinatorial optimization. Polyhedra and efficiency (3 volumes)
- A 1.488 approximation algorithm for the uncapacitated facility location problem
- A 5-Approximation for Capacitated Facility Location
- Sherali-Adams Gaps, Flow-cover Inequalities and Generalized Configurations for Capacity-constrained Facility Location.
- The Design of Approximation Algorithms
- A Hierarchy of Relaxations between the Continuous and Convex Hull Representations for Zero-One Programming Problems
- 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
- Fault-Tolerant Facility Location: A Randomized Dependent LP-Rounding Algorithm
- A new greedy approach for facility location problems
- Faces for a linear inequality in 0–1 variables
- Greedy Strikes Back: Improved Facility Location Algorithms
- Improved Approximation Algorithms for the Uncapacitated Facility Location Problem
- Analysis of a Local Search Heuristic for Facility Location Problems
- A General Approximation Technique for Constrained Forest Problems
- When Trees Collide: An Approximation Algorithm for the Generalized Steiner Problem on Networks
- Capacitated Facility Location: Valid Inequalities and Facets
- On Allocating Goods to Maximize Fairness
- Approximation Algorithms for the Multi-item Capacitated Lot-Sizing Problem Via Flow-Cover Inequalities
- Approximating k-median via pseudo-approximation
- An Optimal Bifactor Approximation Algorithm for the Metric Uncapacitated Facility Location Problem
- Approximation, Randomization, and Combinatorial Optimization.. Algorithms and Techniques
This page was built for publication: LP-Based Algorithms for Capacitated Facility Location
