Weizmann Logo
ECCC
Electronic Colloquium on Computational Complexity

Under the auspices of the Computational Complexity Foundation (CCF)

Login | Register | Classic Style



REPORTS > KEYWORD > MIXED-INTEGER ROUNDING:
Reports tagged with mixed-integer rounding:
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