The Space Complexity of Cutting Planes Refutations.
Nicola GalesiPavel PudlákNeil ThapenPublished in: Computational Complexity Conference (2015)
Keyphrases
- space complexity
- cutting plane
- cutting plane algorithm
- integer programming
- lower bound
- column generation
- worst case
- integer programming problems
- integer program
- arc consistency
- valid inequalities
- knapsack problem
- mixed integer
- space requirements
- branch and bound
- mathematical model
- particle swarm optimization algorithm
- search algorithm
- network flow
- upper bound
- worst case time complexity
- dantzig wolfe decomposition