|
Published Articles >> Table of Contents >> Abstract
44th Annual IEEE Symposium on Foundations of Computer Science (FOCS'03)
p. 318
Rank Bounds and Integrality Gaps for Cutting Planes Procedures
Joshua Buresh-Oppenheim, University of Toronto
Nicola Galesi, Universitat Politecnica de Catalunya
Shlomo Hoory, University of Toronto
Avner Magen, University of Toronto
Toniann Pitassi, University of Toronto
Full Article Text:
  
DOI Bookmark: http://doi.ieeecomputersociety.org/10.1109/SFCS.2003.1238206
Send link to a friend
| Abstract |
|
We present a new method for proving rank lower bounds for Cutting Planes (CP) and several procedures based on lifting due to 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 Cutting Planes and Lovász-Schrijver 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 CP or LS procedures when applied to relaxations of integer linear programs is not sufficient for reducing the integrality gap. Secondly, we give unsatisfiable examples that have constant rank CP and LS proofs but that require linear rank Resolution proofs. Thirdly, we give examples where the CP 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 with polynomial-size CP/LS proofs, but requiring linear rank.
|
 Additional Information
|
Citation:
Joshua Buresh-Oppenheim, Nicola Galesi, Shlomo Hoory, Avner Magen, Toniann Pitassi,
"Rank Bounds and Integrality Gaps for Cutting Planes Procedures,"
focs,
p. 318,
44th Annual IEEE Symposium on Foundations of Computer Science (FOCS'03),
2003
|
|
