Exponential Lower Bounds and Integrality Gaps for Tree-Like Lovász–Schrijver Procedures
From MaRDI portal
Publication:2884578
DOI10.1137/100816833zbMath1242.68117MaRDI 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
90C22: Semidefinite programming
90C57: Polyhedral combinatorics, branch-and-bound, branch-and-cut
68Q17: Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.)
03F20: Complexity of proofs
Related Items
Size-degree trade-offs for sums-of-squares and positivstellensatz proofs, Circular (Yet Sound) Proofs in Propositional Logic, Towards NP-P via proof complexity and search, Rank bounds for a hierarchy of Lovász and Schrijver, Tight rank lower bounds for the Sherali-Adams proof system, Tight size-degree bounds for sums-of-squares proofs, Rank complexity gap for Lovász-Schrijver and Sherali-Adams proof systems, Integrality Gaps of Linear and Semi-Definite Programming Relaxations for Knapsack