Integrality gaps for strengthened linear relaxations of capacitated facility location
From MaRDI portal
Publication:304227
DOI10.1007/s10107-015-0916-zzbMath1343.90048OpenAlexW2170966701MaRDI QIDQ304227
Yannis Moysoglou, Stavros G. Kolliopoulos
Publication date: 25 August 2016
Published in: Mathematical Programming. Series A. Series B (Search for Journal in Brave)
Full work available at URL: https://doi.org/10.1007/s10107-015-0916-z
Related Items
Integrality gaps for strengthened linear relaxations of capacitated facility location, Lift \& project systems performing on the partial-vertex-cover polytope
Cites Work
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Integrality gaps for strengthened linear relaxations of capacitated facility location
- A 3-approximation algorithm for the facility location problem with uniform capacities
- LP-based approximation algorithms for capacitated facility location
- Centrality of trees for capacitated \(k\)-center
- Valid inequalities for mixed integer linear programs
- Expressing combinatorial optimization problems by linear programs
- Valid inequalities and facets of the capacitated plant location problem
- Improved approximation algorithms for capacitated facility location problems
- The 2-valued case of makespan minimization with assignment constraints
- A 1.488 approximation algorithm for the uncapacitated facility location problem
- A lift-and-project cutting plane algorithm for mixed 0-1 programs
- A 5-Approximation for Capacitated Facility Location
- The Santa Claus problem
- Extended Formulation Lower Bounds via Hypergraph Coloring
- LP-Based Algorithms for Capacitated Facility Location
- Sherali-Adams Gaps, Flow-cover Inequalities and Generalized Configurations for Capacity-constrained Facility Location.
- The Design of Approximation Algorithms
- Approximate Constraint Satisfaction Requires Large LP Relaxations
- Assignment problem in content distribution networks
- A Hierarchy of Relaxations between the Continuous and Convex Hull Representations for Zero-One Programming Problems
- Approximation Algorithms for Metric Facility Location Problems
- Greedy facility location algorithms analyzed using dual fitting with factor-revealing LP
- 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
- Heuristics for the fixed cost median problem
- Cones of Matrices and Set-Functions and 0–1 Optimization
- Greedy Strikes Back: Improved Facility Location Algorithms
- The Matching Polytope has Exponential Extension Complexity
- Capacitated Facility Location: Valid Inequalities and Facets
- Santa Claus Schedules Jobs on Unrelated Machines
- Integrality gaps for Sherali-Adams relaxations
- Sherali-adams relaxations of the matching polytope
- Approximating k-median via pseudo-approximation
- When Does the Positive Semidefiniteness Constraint Help in Lifting Procedures?
- A Comparison of the Sherali-Adams, Lovász-Schrijver, and Lasserre Relaxations for 0–1 Programming
- Integer Programming and Combinatorial Optimization
- Algorithms - ESA 2003
- Extended formulations in combinatorial optimization
