ECCC-Report TR12-041https://eccc.weizmann.ac.il/report/2012/041Comments and Revisions published for TR12-041en-usSat, 29 Sep 2012 13:24:14 +0200
Revision 1
| Limitations of Incremental Dynamic Programming |
Stasys Jukna
https://eccc.weizmann.ac.il/report/2012/041#revision1We 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.Sat, 29 Sep 2012 13:24:14 +0200https://eccc.weizmann.ac.il/report/2012/041#revision1
Paper TR12-041
| Limitations of Incremental Dynamic Programs |
Stasys Jukna
https://eccc.weizmann.ac.il/report/2012/041We 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.Tue, 17 Apr 2012 20:18:23 +0300https://eccc.weizmann.ac.il/report/2012/041