• Table design in dynamic progra...

Result: Table design in dynamic programming

Title:
Table design in dynamic programming
Authors:
STEFFEN, Peter, GIEGERICH, Robert
Source:
Information and computation (Print). 204(9):1325-1345
Publisher Information:
San Diego, CA: Elsevier, 2006.
Publication Year:
2006
Physical Description:
print, 27 ref
Original Material:
INIST-CNRS
Subject Terms:
Computer science, Informatique, Sciences exactes et technologie, Exact sciences and technology, Sciences et techniques communes, Sciences and techniques of general use, Mathematiques, Mathematics, Analyse numérique. Calcul scientifique, Numerical analysis. Scientific computation, Analyse numérique, Numerical analysis, Méthodes numériques en programmation mathématique, optimisation et calcul variationnel, Numerical methods in mathematical programming, optimization and calculus of variations, Sciences appliquees, Applied sciences, Informatique; automatique theorique; systemes, Computer science; control theory; systems, Informatique théorique, Theoretical computing, Algorithmique. Calculabilité. Arithmétique ordinateur, Algorithmics. Computability. Computer arithmetics, Théorie programmation, Programming theory, Algorithme, Algorithm, Algoritmo, Approche heuristique, Heuristic approach, Enfoque heurístico, Conception, Design, Diseño, Efficacité asymptotique, Asymptotic efficiency, Eficacia asintótica, Espace temps, Space time, Espacio tiempo, Informatique théorique, Computer theory, Informática teórica, Optimisation combinatoire, Combinatorial optimization, Optimización combinatoria, Problème NP complet, NP complete problem, Problema NP completo, Programmation dynamique, Dynamic programming, Programación dinámica, Relation récurrence, Recurrence relation, Relación recurrencia, Solution optimale, Optimal solution, Solución óptima, Stratégie, Strategy, Estrategia, Méthodologie programmation, Programming methodology, Programmation combinatoire, Tabulation, NP completeness, Space-time trade-off
Document Type:
Academic journal Article
File Description:
text
Language:
English
Author Affiliations:
Faculty of Technology, Bielefeld University, Postfach 10 01 31, 33501 Bielefeld, Germany
ISSN:
0890-5401
Access URL:
http://pascal-francis.inist.fr/vibad/index.php?action=search&terms=18122364
Rights:
Copyright 2006 INIST-CNRS
CC BY 4.0
Sauf mention contraire ci-dessus, le contenu de cette notice bibliographique peut être utilisé dans le cadre d’une licence CC BY 4.0 Inist-CNRS / Unless otherwise stated above, the content of this bibliographic record may be used under a CC BY 4.0 licence by Inist-CNRS / A menos que se haya señalado antes, el contenido de este registro bibliográfico puede ser utilizado al amparo de una licencia CC BY 4.0 Inist-CNRS
Notes:
Computer science; theoretical automation; systems

Mathematics
Accession Number:
edscal.18122364
Database:
PASCAL Archive

Further Information

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.