Table design in dynamic programming

Steffen P, Giegerich R (2006)
INFORMATION AND COMPUTATION 204(9): 1325-1345.

Journal Article | Published | English

No fulltext has been uploaded

Abstract
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.
Publishing Year
ISSN
PUB-ID

Cite this

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.
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.
This data publication is cited in the following publications:
This publication cites the following data publications:

Export

0 Marked Publications

Open Data PUB

Web of Science

View record in Web of Science®

Search this title in

Google Scholar