The space complexity of cutting planes refutations.
Nicola GalesiPavel PudlákNeil ThapenPublished in: Electron. Colloquium Comput. Complex. (2014)
Keyphrases
- space complexity
- cutting plane
- cutting plane algorithm
- integer programming
- lower bound
- integer programming problems
- column generation
- worst case
- integer program
- arc consistency
- mixed integer
- space requirements
- knapsack problem
- dantzig wolfe decomposition
- valid inequalities
- worst case time complexity
- linear program
- upper bound
- bayesian networks
- fine grained
- np hard
- data structure