Exponential Lower Bounds and Integrality Gaps for Tree-Like Lovász–Schrijver Procedures
From MaRDI portal
Publication:2884578
DOI10.1137/100816833zbMath1242.68117OpenAlexW1981949200MaRDI QIDQ2884578
Nathan Segerlind, Toniann Pitassi
Publication date: 30 May 2012
Published in: SIAM Journal on Computing (Search for Journal in Brave)
Full work available at URL: https://doi.org/10.1137/100816833
Semidefinite programming (90C22) Polyhedral combinatorics, branch-and-bound, branch-and-cut (90C57) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Complexity of proofs (03F20)
Related Items (8)
Tight size-degree bounds for sums-of-squares proofs ⋮ Towards NP-P via proof complexity and search ⋮ Circular (Yet Sound) Proofs in Propositional Logic ⋮ Rank complexity gap for Lovász-Schrijver and Sherali-Adams proof systems ⋮ Rank bounds for a hierarchy of Lovász and Schrijver ⋮ Integrality Gaps of Linear and Semi-Definite Programming Relaxations for Knapsack ⋮ Tight rank lower bounds for the Sherali-Adams proof system ⋮ Size-degree trade-offs for sums-of-squares and positivstellensatz proofs
This page was built for publication: Exponential Lower Bounds and Integrality Gaps for Tree-Like Lovász–Schrijver Procedures
