Conference paper
A quantitative analysis of OS noise
Alessandro Morari, Roberto Gioiosa, et al.
IPDPS 2011
We examine the complexity of branch-and-cut proofs in the context of 0-1 integer programs. We establish an exponential lower bound on the length of branch-and-cut proofs that use 0-1 branching and lift-and-project cuts (called simple disjunctive cuts by some authors), Gomory-Chvátal cuts, and cuts arising from the N0 matrix-cut operator of Lovász and Schrijver. A consequence of the lower-bound result in this paper is that branch-and-cut methods of the type described above have exponential running time in the worst case. © 2005 INFORMS.
Alessandro Morari, Roberto Gioiosa, et al.
IPDPS 2011
Marshall W. Bern, Howard J. Karloff, et al.
Theoretical Computer Science
Inbal Ronen, Elad Shahar, et al.
SIGIR 2009
Liqun Chen, Matthias Enzmann, et al.
FC 2005