  We study the incremental knapsack problem, where one wishes to sequentially
pack items into a knapsack whose capacity expands over a finite planning
horizon, with the objective of maximizing time-averaged profits. While various
approximation algorithms were developed under mitigating structural
assumptions, obtaining non-trivial performance guarantees for this problem in
its utmost generality has remained an open question thus far. In this paper, we
devise a polynomial-time approximation scheme for general instances of the
incremental knapsack problem, which is the strongest guarantee possible given
existing hardness results. In contrast to earlier work, our algorithmic
approach exploits an approximate dynamic programming formulation. Starting with
a simple exponentially sized dynamic program, we prove that an appropriate
composition of state pruning ideas yields a polynomially sized state space with
negligible loss of optimality. The analysis of this formulation synthesizes
various techniques, including new problem decompositions, parsimonious counting
arguments, and efficient rounding methods, that may be of broader interest.
