Rank Lower Bounds for the Sherali-Adams Operator

DOI10.1007/978-3-540-73001-9_67MaRDI QIDQ5425367zbMATH OpenOpenAlexFDO

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

zbMATH Keywords

Lift and Project Proof SystemsPropositional Proof ComplexityRank Lower BoundsSherali-Adams Relaxation

Mathematics Subject Classification ID

Integer programming (90C10) Mechanization of proofs and logical operations (03B35) Complexity of proofs (03F20)

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

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)