Weizmann Logo
ECCC
Electronic Colloquium on Computational Complexity

Under the auspices of the Computational Complexity Foundation (CCF)

Login | Register | Classic Style



REPORTS > DETAIL:

Revision(s):

Revision #1 to TR12-041 | 29th September 2012 13:24

Limitations of Incremental Dynamic Programming

RSS-Feed




Revision #1
Authors: Stasys Jukna
Accepted on: 29th September 2012 13:24
Downloads: 3131
Keywords: 


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).


Paper:

TR12-041 | 17th April 2012 20:16

Limitations of Incremental Dynamic Programs





TR12-041
Authors: Stasys Jukna
Publication: 17th April 2012 20:18
Downloads: 3731
Keywords: 


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.



ISSN 1433-8092 | Imprint