On the width of semialgebraic proofs and algorithms

DOI10.1287/MOOR.2016.0840MaRDI QIDQ4595958zbMATH OpenOpenAlexWikidataFDO

Authors Alexander Razborov

Publication date 7 December 2017

Published in Mathematics of Operations Research (Search for Journal in Brave)

Full work available at URL https://semanticscholar.org/paper/ab506cbba22d7267f7770b7b5b5c6853c2314c6e

zbMATH Keywords

cutting planesLovasz-Schrijverproof complexityproof width

Mathematics Subject Classification ID

Complexity of proofs (03F20) Combinatorial optimization (90C27)

Recommendations

• scientific article; zbMATH DE number 2086404
• scientific article; zbMATH DE number 1916823
• Several notes on the power of Gomory-Chvátal cuts
• Rank bounds and integrality gaps for cutting planes procedures
• scientific article; zbMATH DE number 2086627

Cited in

(14)

• On space and depth in resolution
• Complexity of branch-and-bound and cutting planes in mixed-integer optimization. II
• Complexity of branch-and-bound and cutting planes in mixed-integer optimization
• scientific article; zbMATH DE number 4024785 (Why is no real title available?)
• scientific article; zbMATH DE number 2086404 (Why is no real title available?)
• scientific article; zbMATH DE number 1916823 (Why is no real title available?)
• Semialgebraic Proofs and Efficient Algorithm Design
• The proof-search problem between bounded-width resolution and bounded-degree semi-algebraic proofs
• Complexity of optimizing over the integers
• Perfect matching in random graphs is as hard as Tseitin
• Proof complexity and beyond. Abstracts from the workshop held March 24--29, 2024
• Cutting planes width and the complexity of graph isomorphism refutations
• Complexity of branch-and-bound and cutting planes in mixed-integer optimization. II
• On the power and limitations of branch and cut

This page was built for publication: On the width of semialgebraic proofs and algorithms

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