Integrality gaps for strengthened linear relaxations of capacitated facility location
type: Item
instance of: scholarly article
title: Integrality gaps for strengthened linear relaxations of capacitated facility location
zbMATH Open document ID: 1343.90048
author: Stavros G. Kolliopoulos
author: Yannis Moysoglou
published in: Mathematical Programming. Series A. Series B
publication date: 2016-08-25T00:00:00Z
Mathematics Subject Classification ID: 90B80
zbMATH DE Number: 6619160
zbMATH Keywords: operations research
zbMATH Keywords: mathematical programming
zbMATH Keywords: discrete location and assignment
MaRDI profile type: Publication
full work available at URL: s10107-015-0916-z
OpenAlex ID: W2170966701
cites work: Capacitated Facility Location: Valid Inequalities and Facets
cites work: Q4880888
cites work: Greedy facility location algorithms analyzed using dual fitting with factor-revealing LP
cites work: A 3-approximation algorithm for the facility location problem with uniform capacities
cites work: Centrality of trees for capacitated \(k\)-center
cites work: LP-Based Algorithms for Capacitated Facility Location
cites work: Q3002764
cites work: A lift-and-project cutting plane algorithm for mixed 0-1 programs
cites work: A 5-Approximation for Capacitated Facility Location
cites work: The Santa Claus problem
cites work: Assignment problem in content distribution networks
cites work: Primal-Dual Schema for Capacitated Covering Problems
cites work: Q4952606
cites work: Approximate Constraint Satisfaction Requires Large LP Relaxations
cites work: Integrality gaps for Sherali-Adams relaxations
cites work: Q4252386
cites work: Improved approximation algorithms for capacitated facility location problems
cites work: Extended formulations in combinatorial optimization
cites work: Valid inequalities for mixed integer linear programs
cites work: Q2934582
cites work: When Does the Positive Semidefiniteness Constraint Help in Lifting Procedures?
cites work: Greedy Strikes Back: Improved Facility Location Algorithms
cites work: Heuristics for the fixed cost median problem
cites work: Approximation algorithms for metric facility location and k -Median problems using the primal-dual schema and Lagrangian relaxation
cites work: Extended Formulation Lower Bounds via Hypergraph Coloring
cites work: The 2-valued case of makespan minimization with assignment constraints
cites work: Sherali-Adams Gaps, Flow-cover Inequalities and Generalized Configurations for Capacity-constrained Facility Location.
cites work: Q4250157
cites work: Q4537750
cites work: A Comparison of the Sherali-Adams, Lovász-Schrijver, and Lasserre Relaxations for 0–1 Programming
cites work: Valid inequalities and facets of the capacitated plant location problem
cites work: LP-based approximation algorithms for capacitated facility location
cites work: A 1.488 approximation algorithm for the uncapacitated facility location problem
cites work: Approximating k-median via pseudo-approximation
cites work: Cones of Matrices and Set-Functions and 0–1 Optimization
cites work: Algorithms - ESA 2003
cites work: Approximation Algorithms for Metric Facility Location Problems
cites work: Sherali-adams relaxations of the matching polytope
cites work: Q4527015
cites work: The Matching Polytope has Exponential Extension Complexity
cites work: Q3549626
cites work: A Hierarchy of Relaxations between the Continuous and Convex Hull Representations for Zero-One Programming Problems
cites work: Q4526991
cites work: Santa Claus Schedules Jobs on Unrelated Machines
cites work: The Design of Approximation Algorithms
cites work: Expressing combinatorial optimization problems by linear programs
cites work: Integer Programming and Combinatorial Optimization
DOI: 10.1007/S10107-015-0916-Z
description: scientific article; zbMATH DE number 6619160