Tight Complexity Lower Bounds for Integer Linear Programming with Few Constraints.
Dusan KnopMichal PilipczukMarcin WrochnaPublished in: STACS (2019)
Keyphrases
- lower bound
- integer linear programming
- worst case
- linear inequalities
- upper bound
- pseudo boolean
- global constraints
- cutting plane
- column generation
- branch and bound
- lower and upper bounds
- bicriteria
- symmetry breaking
- exact solution
- branch and bound algorithm
- constraint programming
- average case complexity
- optimal solution
- objective function
- space complexity
- constraint satisfaction
- np hard
- boolean satisfiability
- linear programming
- computational complexity
- greedy algorithm
- constraint satisfaction problems
- dynamic programming
- boolean optimization