On the complexity of cutting-plane proofs using split cuts |
| |
| Authors: | Sanjeeb Dash |
| |
| Institution: | IBM T. J. Watson Research Center, 1101 Kitchawan Road, Yorktown Heights, NY 10598, United States |
| |
| Abstract: | We prove a monotone interpolation property for split cuts which, together with results from Pudlák (1997) 20], implies that cutting-plane proofs which use split cuts (or, equivalently, mixed-integer rounding cuts or Gomory mixed-integer cuts) have exponential length in the worst case. |
| |
| Keywords: | Cutting-plane proof Split cut Mixed-integer rounding Monotone interpolation |
| 本文献已被 ScienceDirect 等数据库收录！ |
|
