Approximation Algorithms for the Incremental Knapsack Problem via Disjunctive Programming

Daniel Bienstock, Jay Sethuraman, Chun Ye

In the 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 t…