Weizmann Logo
ECCC
Electronic Colloquium on Computational Complexity

Under the auspices of the Computational Complexity Foundation (CCF)

Login | Register | Classic Style



REPORTS > DETAIL:

Paper:

TR08-084 | 16th June 2008 00:00

On the complexity of cutting plane proofs using split cuts

RSS-Feed




TR08-084
Authors: Sanjeeb Dash
Publication: 17th September 2008 08:55
Downloads: 2994
Keywords: 


Abstract:

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 also have exponential worst-case complexity.



ISSN 1433-8092 | Imprint