On the Width of Semialgebraic Proofs and Algorithms

Alexander Razborov ()
Additional contact information
Alexander Razborov: Departments of Mathematics and Computer Science, University of Chicago, Chicago, Illinois 60637; and Steklov Mathematical Institute, Moscow, Russia 117418

Mathematics of Operations Research, 2017, vol. 42, issue 4, 1106-1134

Abstract: In this paper we study width of semialgebraic proof systems and various cut-based procedures in integer programming. We focus on two important systems: Gomory-Chvátal cutting planes and Lovász-Schrijver lift-and-project procedures. We develop general methods for proving width lower bounds and apply them to random k-CNFs and several popular combinatorial principles, like the perfect matching principle and Tseitin tautologies. We also show how to apply our methods to various combinatorial optimization problems. We establish a “supercritical” trade-off between width and rank, that is we give an example in which small width proofs are possible but require exponentially many rounds to perform them.

Keywords: cutting planes; Lovasz-Schrijver; proof width; proof complexity (search for similar items in EconPapers)
Date: 2017
References: View references in EconPapers View complete reference list from CitEc
Citations:

Downloads: (external link)
https://doi.org/10.1287/moor.2016.0840 (application/pdf)

Related works:
This item may be available elsewhere in EconPapers: Search for items with the same title.

Export reference: BibTeX RIS (EndNote, ProCite, RefMan) HTML/Text

Persistent link: https://EconPapers.repec.org/RePEc:inm:ormoor:v:42:y:2017:i:4:p:1106-1134

Access Statistics for this article

More articles in Mathematics of Operations Research from INFORMS Contact information at EDIRC.
Bibliographic data for series maintained by Chris Asher ().