Tight Complexity Lower Bounds for Integer Linear Programming with Few Constraints.
Dusan KnopMichal PilipczukMarcin WrochnaPublished in: ACM Trans. Comput. Theory (2020)
Keyphrases
- lower bound
- integer linear programming
- worst case
- linear inequalities
- upper bound
- cutting plane
- pseudo boolean
- global constraints
- column generation
- branch and bound
- lower and upper bounds
- bicriteria
- branch and bound algorithm
- symmetry breaking
- integer program
- exact solution
- np hard
- average case complexity
- optimal solution
- objective function
- computational complexity
- perfect phylogeny
- max sat
- space complexity
- greedy algorithm
- constraint programming
- optimization problems
- search algorithm