A rank lower bound for cutting planes proofs of Ramsey Theorem.
Massimo LauriaPublished in: Electron. Colloquium Comput. Complex. (2012)
Keyphrases
- lower bound
- cutting plane
- interactive theorem proving
- upper bound
- cutting plane algorithm
- integer programming problems
- branch and bound algorithm
- lower and upper bounds
- np hard
- branch and bound
- objective function
- linear programming relaxation
- optimal solution
- worst case
- valid inequalities
- lagrangian relaxation
- special case
- column generation
- integer programming
- knapsack problem