Rank bounds for a hierarchy of Lovász and Schrijver
type: Item
instance of: scholarly article
title: Rank bounds for a hierarchy of Lovász and Schrijver
zbMATH Open document ID: 1353.90088
author: Pratik Worah
published in: Journal of Combinatorial Optimization
publication date: 2015-09-28T00:00:00Z
Mathematics Subject Classification ID: 90C09
zbMATH DE Number: 6485836
zbMATH Keywords: linear programming
zbMATH Keywords: integrality gaps
zbMATH Keywords: proof complexity
MaRDI profile type: Publication
full work available at URL: s10878-013-9662-4
OpenAlex ID: W2159431940
cites work: Complexity Analyses of Bienstock–Zuckerberg and Lasserre Relaxations on the Matching and Stable Set Polytopes
cites work: Hardness amplification in proof complexity
cites work: SDP gaps from pairwise independence
cites work: Q4821526
cites work: Q3002766
cites work: Integrality gaps for Sherali-Adams relaxations
cites work: Computation of the Lasserre Ranks of Some Polytopes
cites work: On a representation of the matching polytope via semidefinite liftings
cites work: On the matrix-cut rank of polyhedra.
cites work: Tight rank lower bounds for the Sherali-Adams proof system
cites work: Q2934582
cites work: On the membership problem for the elementary closure of a polyhedron
cites work: When Does the Positive Semidefiniteness Constraint Help in Lifting Procedures?
cites work: Q4736859
cites work: Unification of lower-bound analyses of the lift-and-project rank of combinatorial optimization polyhedra
cites work: Q4856172
cites work: A Comparison of the Sherali-Adams, Lovász-Schrijver, and Lasserre Relaxations for 0–1 Programming
cites work: Cones of Matrices and Set-Functions and 0–1 Optimization
cites work: Sherali-adams relaxations of the matching polytope
cites work: Exponential lower bounds and integrality gaps for tree-like Lovász-Schrijver procedures
cites work: Q4934563
cites work: Q4737899
cites work: Q4822945
cites work: The Complexity of Propositional Proofs
cites work: A Hierarchy of Relaxations between the Continuous and Convex Hull Representations for Zero-One Programming Problems
cites work: Exploiting special structures in constructing a hierarchy of relaxations for \(0-1\) mixed integer problems
DOI: 10.1007/S10878-013-9662-4
description: scientific article; zbMATH DE number 6485836