Integrality gaps for strengthened linear relaxations of capacitated facility location

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

zbMATH Keywords

mathematical programmingoperations researchdiscrete location and assignment

Mathematics Subject Classification ID

Discrete location and assignment (90B80)

Related Items (2)

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

This page was built for publication: Integrality gaps for strengthened linear relaxations of capacitated facility location