Weizmann Logo
ECCC
Electronic Colloquium on Computational Complexity

Under the auspices of the Computational Complexity Foundation (CCF)

Login | Register | Classic Style



REPORTS > KEYWORD > CUTTING-PLANE PROOF:
Reports tagged with cutting-plane proof:
TR08-084 | 16th June 2008
Sanjeeb Dash

On the complexity of cutting plane proofs using split cuts

We prove a monotone interpolation property for split cuts which, together with results from Pudlak (1997), implies that cutting-plane proofs which use split cuts have exponential length in the worst case.
As split cuts are equivalent to mixed-integer rounding cuts and Gomory mixed-integer cuts, cutting-plane proofs using the above cuts ... more >>>




ISSN 1433-8092 | Imprint