Approximation Algorithms for the Incremental Knapsack Problem via Disjunctive Programming
In the \emph{incremental knapsack problem} ($\IK$), we are given a knapsack whose capacity grows weakly as a function of time. There is a time horizon of $T$ periods and the capacity of the knapsack is $B_t$ in period $t$ for $t = 1, \ldots, T$. We are also given a set $S$ of $N$ items … Read more