التفاصيل البيبلوغرافية
| العنوان: |
On the Width of Semialgebraic Proofs and Algorithms. |
| المؤلفون: |
Razborov, Alexander1 |
| المصدر: |
Mathematics of Operations Research. Nov2017, Vol. 42 Issue 4, p1106-1134. 29p. |
| مصطلحات موضوعية: |
*INTEGER programming, MATHEMATICAL proofs, ALGEBRAIC geometry, MATHEMATICAL bounds, COMBINATORICS |
| مستخلص: |
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. [ABSTRACT FROM AUTHOR] |
|
Copyright of Mathematics of Operations Research is the property of INFORMS: Institute for Operations Research and its content may not be copied or emailed to multiple sites or posted to a listserv without the copyright holder's express written permission. However, users may print, download, or email articles for individual use. This abstract may be abridged. No warranty is given about the accuracy of the copy. Users should refer to the original published version of the material for the full abstract. (Copyright applies to all Abstracts.) |
| قاعدة البيانات: |
Business Source Index |
