Volume 2 (2006) Article 4 pp. 65-90

Rank Bounds and Integrality Gaps for Cutting Planes Procedures

by Joshua Buresh-Oppenheim, Nicola Galesi, Shlomo Hoory, Avner Magen, and Toniann Pitassi

Received: May 6, 2005
Published: March 25, 2006
DOI: 10.4086/toc.2006.v002a004

Download article from ToC site:
[PS (545K)]    [PS.GZ (131K)]    [PS.ZIP (131K)]
[PDF (276K)]    [DVI (232K)]    [ZIP (35K)]
Misc.:
[HTML Bibliography] [Bibliography Source] [BibTeX] 
[About the Author(s)]
Keywords: cutting planes, proof complexity, approximation algorithms
Categories: complexity theory, proof complexity, algorithms, approximation algorithms, integrality gap, rank, lower bounds, formulas, Boolean formulas, CNF-DNF formulas
ACM Classification: G.1.6, F.4.1, F.1.3
AMS Classification: 68Q25, 03F20, 90C05, 90C09

Abstract: [Plain Text Version]

We present a new method for proving rank lower bounds for the cutting planes procedures of Gomory and Chvátal (GC) and Lovász and Schrijver (LS), when viewed as proof systems for unsatisfiability. We apply this method to obtain the following new results:

First, we prove near-optimal rank bounds for GC and LS proofs for several prominent unsatisfiable CNF examples, including random kCNF formulas and the Tseitin graph formulas. It follows from these lower bounds that a linear number of rounds of GC or LS procedures when applied to the standard MAXSAT linear relaxation does not reduce the integrality gap.

Second, we give unsatisfiable examples that have constant rank GC and LS proofs but that require linear rank Resolution proofs.

Third, we give examples where the GC rank is O(log n) but the LS rank is linear.

Finally, we address the question of size versus rank; we show that, for both proof systems, rank does not accurately reflect proof size. Specifically, there are examples which have polynomial-size GC/LS proofs but require linear rank.