Rank Lower Bounds for the Sherali-Adams Operator
DOI10.1007/978-3-540-73001-9_67zbMATH Open1150.03339OpenAlexW1557126113MaRDI QIDQ5425367FDOQ5425367
Authors: Mark Rhodes 
Publication date: 13 November 2007
Published in: Lecture Notes in Computer Science (Search for Journal in Brave)
Full work available at URL: https://doi.org/10.1007/978-3-540-73001-9_67
Recommendations
- Tight rank lower bounds for the Sherali-Adams proof system
- Rank complexity gap for Lovász-Schrijver and Sherali-Adams proof systems
- Rank complexity gap for Lovász-Schrijver and Sherali-Adams proof systems
- On the rank of cutting-plane proof systems
- Rank bounds and integrality gaps for cutting planes procedures
Lift and Project Proof SystemsPropositional Proof ComplexityRank Lower BoundsSherali-Adams Relaxation
Integer programming (90C10) Mechanization of proofs and logical operations (03B35) Complexity of proofs (03F20)
Cited In (5)
- Resolution Width and Cutting Plane Rank Are Incomparable
- Proof complexity and the binary encoding of combinatorial principles
- On the Chvátal rank of the pigeonhole principle
- On the strength of Sherali-Adams and Nullstellensatz as propositional proof systems
- Tight rank lower bounds for the Sherali-Adams proof system
This page was built for publication: Rank Lower Bounds for the Sherali-Adams Operator
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q5425367)
