On the Chvátal rank of the pigeonhole principle

DOI10.1016/j.tcs.2009.03.035zbMath1169.03045OpenAlexW2061307063MaRDI QIDQ1029351

Mark Rhodes

Publication date: 10 July 2009

Published in: Theoretical Computer Science (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1016/j.tcs.2009.03.035

zbMATH Keywords

cutting planespropositional proof complexityChvátal rankpigeonhole principle

Mathematics Subject Classification ID

Integer programming (90C10) Complexity of proofs (03F20)

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• On the complexity of cutting-plane proofs
• The intractability of resolution
• A complexity gap for tree resolution
• Edmonds polytopes and a hierarchy of combinatorial problems
• A Hierarchy of Relaxations between the Continuous and Convex Hull Representations for Zero-One Programming Problems
• Outline of an algorithm for integer solutions to linear programs
• Cones of Matrices and Set-Functions and 0–1 Optimization
• Rank Lower Bounds for the Sherali-Adams Operator

This page was built for publication: On the Chvátal rank of the pigeonhole principle