Abstract / Bemerkung
Dynamic Programming solves combinatorial optimization problems by recursive decomposition and tabulation of intermediate results. The first step in the design of a dynamic programming algorithm is to decide on the set of tables that will hold optimal solutions to subproblems. This step predetermines the shape of the dynamic programming recurrences as well as the asymptotic efficiency of the algorithm in time and space. We study dynamic programming in a formal framework where design of tables and problem decomposition can be done independently. Our main result shows that choosing a good table design for a given decomposition is an NP-complete problem. A heuristic or approximate approach is therefore needed to automate good table design. We report on a strategy that combines user annotation and a brute force algorithm, which is shown to perform well in a large application. (C) 2006 Elsevier Inc. All rights reserved.
programming methodology; dynamic programming; space-time trade-off; NP completeness
INFORMATION AND COMPUTATION
Steffen P, Giegerich R. Table design in dynamic programming. INFORMATION AND COMPUTATION. 2006;204(9):1325-1345.
Steffen, P., & Giegerich, R. (2006). Table design in dynamic programming. INFORMATION AND COMPUTATION, 204(9), 1325-1345. doi:10.1016/j.ic.2006.02.006
Steffen, P., and Giegerich, R. (2006). Table design in dynamic programming. INFORMATION AND COMPUTATION 204, 1325-1345.
Steffen, P., & Giegerich, R., 2006. Table design in dynamic programming. INFORMATION AND COMPUTATION, 204(9), p 1325-1345.
P. Steffen and R. Giegerich, “Table design in dynamic programming”, INFORMATION AND COMPUTATION, vol. 204, 2006, pp. 1325-1345.
Steffen, P., Giegerich, R.: Table design in dynamic programming. INFORMATION AND COMPUTATION. 204, 1325-1345 (2006).
Steffen, Peter, and Giegerich, Robert. “Table design in dynamic programming”. INFORMATION AND COMPUTATION 204.9 (2006): 1325-1345.