Cutting planes and the parameter cutwidth

DOI10.1007/S00224-011-9373-0zbMATH Open1282.03023OpenAlexW2022668562MaRDI QIDQ693047FDOQ693047

Authors Barnaby Martin, Stephan Stoyanov Danchev

Publication date 7 December 2012

Published in Theory of Computing Systems (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1007/s00224-011-9373-0

zbMATH Keywords

cutting planesproof complexity[https://portal.mardi4nfdi.de/w/index.php?title=+Special%3ASearch&search=Chv%EF%BF%BD%EF%BF%BDtal+rank&go=Go Chv��tal rank]

Mathematics Subject Classification ID

Complexity of proofs (03F20)

Recommendations

• Cutting planes and the parameter cutwidth
• Constructing Planar Cuttings in Theory and Practice
• CUTTING PLANE WITH NON-UNIFORM DISTRIBUTIONS
• Theoretical challenges towards cutting-plane selection
• A finitely converging cutting plane technique
• scientific article; zbMATH DE number 4202024
• Cutting planes from extended LP formulations
• A nontangential cutting plane algorithm
• On constants for cuttings in the plane
• One approach to constructing cutting algorithms with dropping of cutting planes

Cites work

• scientific article; zbMATH DE number 3156817 (Why is no real title available?)
• A Hierarchy of Relaxations between the Continuous and Convex Hull Representations for Zero-One Programming Problems
• A combinatorial characterization of resolution width
• A complexity gap for tree resolution
• Bounds on the Chvatal rank of polytopes in the 0/1-cube
• Cutting planes and the parameter cutwidth
• Edmonds polytopes and a hierarchy of combinatorial problems
• On the Chvátal rank of polytopes in the 0/1 cube
• On the complexity of cutting-plane proofs
• Rank bounds and integrality gaps for cutting planes procedures
• Rank complexity gap for Lovász-Schrijver and Sherali-Adams proof systems
• Short proofs are narrow—resolution made simple

Cited in

(8)

• On the lengths of tree-like and dag-like cutting plane refutations of Horn constraint systems. Horn constraint systems and cutting plane refutations
• Achieving consistency with cutting planes
• CUTTING PLANE WITH NON-UNIFORM DISTRIBUTIONS
• Shallow, deep and very deep cuts in the analytic center cutting plane method.
• Resolution Width and Cutting Plane Rank Are Incomparable
• Cutting plane and Frege proofs
• Cutting planes width and the complexity of graph isomorphism refutations
• Cutting planes and the parameter cutwidth

This page was built for publication: Cutting planes and the parameter cutwidth

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q693047)