Name
Abstract | ||
|---|---|---|
We address the problem of effective reuse of subproblem solutions in dynamic programming. In dynamic programming, a memoed solution of a subproblem can be reused for another if the latter's context is a special case of the former. Our objective is to generalize the context of the memoed subproblem such that more subproblems can be considered subcases and hence enhance reuse. Toward this goal we propose a generalization of context that 1) does not add better solutions than the subproblem's optimal, yet 2) requires that subsumed sub-problems preserve the optimal solution. In addition, we also present a general technique to search for at most k ≥ 1 optimal solutions. We provide experimental results on resource-constrained shortest path (RCSP) benchmarks and program's exact worst-case execution time (WCET) analysis. |
Year | Venue | Keywords |
|---|---|---|
2008 | AAAI | general technique,exact worst-case execution time,subproblem solution,optimal solution,resource-constrained shortest path,ad-hoc constraint,efficient memoization,memoed solution,better solution,dynamic programming,effective reuse,worst case execution time,shortest path |
Field | DocType | Citations |
Dynamic programming,Optimal substructure,Mathematical optimization,Shortest path problem,Computer science,Reuse,Execution time,Memoization,Special case | Conference | 12 |
PageRank | References | Authors |
1.02 | 14 | 3 |
Name | Order | Citations | PageRank |
|---|---|---|---|
| Joxan Jaffar | 1 | 2350 | 283.50 |
| Andrew Santosa | 2 | 146 | 13.36 |
| Razvan Voicu | 3 | 57 | 4.22 |