  We introduce and study a discrete multi-period extension of the classical
knapsack problem, dubbed generalized incremental knapsack. In this setting, we
are given a set of $n$ items, each associated with a non-negative weight, and
$T$ time periods with non-decreasing capacities $W_1 \leq \dots \leq W_T$. When
item $i$ is inserted at time $t$, we gain a profit of $p_{it}$; however, this
item remains in the knapsack for all subsequent periods. The goal is to decide
if and when to insert each item, subject to the time-dependent capacity
constraints, with the objective of maximizing our total profit. Interestingly,
this setting subsumes as special cases a number of recently-studied incremental
knapsack problems, all known to be strongly NP-hard.
  Our first contribution comes in the form of a polynomial-time
$(\frac{1}{2}-\epsilon)$-approximation for the generalized incremental knapsack
problem. This result is based on a reformulation as a single-machine sequencing
problem, which is addressed by blending dynamic programming techniques and the
classical Shmoys-Tardos algorithm for the generalized assignment problem.
Combined with further enumeration-based self-reinforcing ideas and
newly-revealed structural properties of nearly-optimal solutions, we turn our
basic algorithm into a quasi-polynomial time approximation scheme (QPTAS).
Hence, under widely believed complexity assumptions, this finding rules out the
possibility that generalized incremental knapsack is APX-hard.
