Speed-Up in Dynamic Programming

DOI10.1137/0603055MaRDI QIDQ3958292zbMATH OpenOpenAlexFDO

Authors F. Frances Yao

Publication date 1982

Published in SIAM Journal on Algebraic Discrete Methods (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1137/0603055

zbMATH Keywords

design of efficient dynamic programming algorithmsgeneral speed-up techniqueoptimal order of multiplying a sequence of matrices

Mathematics Subject Classification ID

Direct numerical methods for linear systems and matrix inversion (65F05) Numerical mathematical programming methods (65K05) Analysis of algorithms and problem complexity (68Q25) Algorithms in computer science (68W99) Dynamic programming (90C39)

Cites work

• Computation of Matrix Chain Products. Part II
• scientific article; zbMATH DE number 3750146 (Why is no real title available?)
• scientific article; zbMATH DE number 3511563 (Why is no real title available?)
• scientific article; zbMATH DE number 3303654 (Why is no real title available?)
• Optimum binary search trees

Cited in

(18)

• Speeding up dynamic programming with applications to molecular biology
• Dynamic programming with convexity, concavity and sparsity
• Monotonicity and efficient computation of optimal dichotomous search
• Dynamic programming and graph optimization problems
• Using geometric techniques to improve dynamic programming algorithms for the economic lot-sizing problem and extensions
• Operations research applications of dichotomous search
• Perspectives of Monge properties in optimization
• Speeding up the AIFV-2 dynamic programs by two orders of magnitude using range minimum queries
• The cone of Monge matrices: Extremal rays and applications
• A dynamic programming approach to power consumption minimization in gunbarrel natural gas networks with nonidentical compressor units
• Revisiting ``Computation of matrix chain products
• On heuristics for minimum length rectilinear partitions
• Optimal binary search trees
• On the parenthesisations of matrix chains: all are useful, few are essential
• Core-sparse Monge matrix multiplication: improved algorithm and applications
• A linear-time algorithm for concave one-dimensional dynamic programming
• An optimal algorithm with unknown time complexity for convex matrix searching
• Trees with exponentially growing costs

This page was built for publication: Speed-Up in Dynamic Programming

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q3958292)