MK's wiki

What is IP? ILP is NP-hard, but maybe restricted instances can be easier?

IP in fixed dimension: flatness theorem, branching, etc.

Building intuition using the knapsack problem and its DP. We can use DP to solve knapsack in time $O(n \cdot b)$, and to solve multidimensional knapsack in $d$ dimensions in time $O(n \cdot b^d)$. But what if $b$ is much larger than the item sizes, and/or what if we are given items by multiplicities $\mu_1, \dots, \mu_n$? Turns out we can start from some solution and then iteratively augment to the optimal solution. Each augmentation requires one DP to be solved, but this DP is simpler than the original one. In the next lecture we will formalize this.