Several notes on the power of Gomory-Chvátal cuts

DOI10.1016/j.apal.2005.12.006zbMath1101.03037OpenAlexW2080045420MaRDI QIDQ2498920

Edward A. Hirsch, Arist Kojevnikov

Publication date: 16 August 2006

Published in: Annals of Pure and Applied Logic (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1016/j.apal.2005.12.006

zbMATH Keywords

linear programminginteger programmingalgebraic proof systemspropositional proof complexity

Mathematics Subject Classification ID

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

Related Items (3)

Randomized feasible interpolation and monotone circuits with a local oracle ⋮ Resolution over linear equations and multilinear proofs ⋮ On the complexity of cutting-plane proofs using split cuts

Cites Work

• On the complexity of cutting-plane proofs
• On cutting-plane proofs in combinatorial optimization
• Stable sets and polynomials
• Algebraic proof systems over formulas.
• A lift-and-project cutting plane algorithm for mixed 0-1 programs
• Edmonds polytopes and a hierarchy of combinatorial problems
• Hard examples for resolution
• Cones of Matrices and Set-Functions and 0–1 Optimization
• The relative efficiency of propositional proof systems
• Discretely ordered modules as a first-order extension of the cutting planes proof system
• Lower bounds for resolution and cutting plane proofs and monotone computations
• Lower Bounds on Hilbert's Nullstellensatz and Propositional Proofs
• Linear gaps between degrees for the polynomial calculus modulo distinct primes
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item

This page was built for publication: Several notes on the power of Gomory-Chvátal cuts