DocumentCode :
2169876
Title :
Rank bounds and integrality gaps for cutting planes procedures
Author :
Buresh-Oppenheim, Joshua ; Galesi, Nicola ; Hoory, Shlomo ; Magen, Avner ; Pitassi, Toniann
Author_Institution :
Toronto Univ., Ont., Canada
fYear :
2003
fDate :
11-14 Oct. 2003
Firstpage :
318
Lastpage :
327
Abstract :
We present a new method for proving rank lower bounds for Cutting Planes (CP) and several procedures based on lifting due to 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 Cutting Planes and Lovasz-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.
Keywords :
boundary integral equations; computability; computational complexity; integer programming; linear programming; theorem proving; CP rank; Lovasz-Schrijver proofs; O(log n); Tseitin graph formulas; cutting planes procedures; integer linear programming; integer linear programs; integrality gap; integrality gaps; linear rank resolution proofs; near-optimal rank bounds; polynomial-size CP/LS proofs; proof systems; random kCNF formulas; rank bound proving; size versus rank; unsatisfiability; unsatisfiable CNF examples; Computer science; Councils; Ellipsoids; Instruments; Integer linear programming; Integral equations; Linear programming; Optimization methods; Polynomials;
fLanguage :
English
Publisher :
ieee
Conference_Titel :
Foundations of Computer Science, 2003. Proceedings. 44th Annual IEEE Symposium on
ISSN :
0272-5428
Print_ISBN :
0-7695-2040-5
Type :
conf
DOI :
10.1109/SFCS.2003.1238206
Filename :
1238206
Link To Document :
بازگشت