Optimal length cutting plane refutations of integer programs

DOI10.1007/978-3-031-25211-2_2OpenAlexW4318023128MaRDI QIDQ6174433

No author found.

Publication date: 17 August 2023

Published in: Algorithms and Discrete Applied Mathematics (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1007/978-3-031-25211-2_2

Mathematics Subject Classification ID

Algorithms in computer science (68Wxx)

Cites Work

• Unnamed Item
• Unnamed Item
• On the complexity of cutting-plane proofs
• The complexity of optimization problems
• In between resolution and cutting planes: a study of proof systems for pseudo-Boolean SAT solving
• Cutting-plane proofs in polynomial space
• On the automatizability of resolution and related propositional proof systems
• Verifying integer programming results
• Edmonds polytopes and a hierarchy of combinatorial problems. (Reprint)
• A Bit-Scaling Algorithm for Integer Feasibility in UTVPI Constraints
• Resolution Is Not Automatizable Unless W[P Is Tractable]
• Lower bounds for cutting planes proofs with small coefficients
• Lower bounds for resolution and cutting plane proofs and monotone computations
• On the approximability of the maximum common subgraph problem
• Automating Resolution is NP-Hard
• Automating cutting planes is NP-hard
• Random \( \Theta (\log n) \) -CNFs are Hard for Cutting Planes
• Tools and Algorithms for the Construction and Analysis of Systems

This page was built for publication: Optimal length cutting plane refutations of integer programs