__
Revision #1 to TR12-041 | 29th September 2012 13:24
__
#### Limitations of Incremental Dynamic Programming

**Abstract:**
We consider so-called ``incremental'' dynamic

programming algorithms, and are interested in the number of subproblems produced by them. The classical dynamic programming algorithm for the n-dimensional Knapsack problem is incremental, produces nK subproblems and nK^2 relations (wires) between the subproblems,

where K is the capacity of the knapsack. We show that any incremental algorithm for this problem must produce about nK subproblems, and that about nK\log K wires (relations between

subproblems) are necessary. We also give upper and lower bounds on the number of subproblems needed to approximate the knapsack problem.

**Changes to previous version:**
Added upper and lower bounds for dynamic branching programs approximating the Knapsack problem (Section 5).

__
TR12-041 | 17th April 2012 20:16
__

#### Limitations of Incremental Dynamic Programs

**Abstract:**
We consider so-called ``incremental'' dynamic programming (DP) algorithms, and are interested in the number of subproblems produced by them. The standard DP algorithm for the n-dimensional Knapsack problem is incremental, and produces nK subproblems, where K is the capacity of the knapsack. We show that any incremental algorithm for this problem must produce about nK subproblems.