Theory of Computing
-------------------
Title : Rank Bounds and Integrality Gaps for Cutting Planes Procedures
Authors : Joshua Buresh-Oppenheim, Nicola Galesi, Shlomo Hoory, Avner Magen, and Toniann Pitassi
Volume : 2
Number : 4
Pages : 65-90
URL : http://www.theoryofcomputing.org/articles/v002a004
Abstract
--------
We present a new method for proving rank lower bounds for
the cutting planes procedures of Gomory and Chvatal (GC)
and Lovasz 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.