Online dynamic programming speedups

DOI10.1007/S00224-009-9166-XMaRDI QIDQ839641zbMATH OpenOpenAlexFDO

Authors Amotz Bar-Noy, Mordecai J. Golin, Yan Zhang

Publication date 2 September 2009

Published in Theory of Computing Systems (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1007/s00224-009-9166-x

zbMATH Keywords

dynamic programmingMonge property

Mathematics Subject Classification ID

Dynamic programming (90C39)

Recommendations

• Online Dynamic Programming Speedups
• The Knuth-Yao quadrangle-inequality speedup is a consequence of total monotonicity
• On-line dynamic programming with applications to the prediction of RNA secondary structure
• Online maintenance of \(k\)-medians and \(k\)-covers on a line
• Algorithm Theory - SWAT 2004

Cites work

• scientific article; zbMATH DE number 1115549 (Why is no real title available?)
• A linear-time algorithm for concave one-dimensional dynamic programming
• Geometric applications of a matrix-searching algorithm
• Monge strikes again: Optimal placement of web proxies in the internet
• On-line dynamic programming with applications to the prediction of RNA secondary structure
• Online maintenance of \(k\)-medians and \(k\)-covers on a line
• Perspectives of Monge properties in optimization
• Speeding up dynamic programming with applications to molecular biology
• The concave least-weight subsequence problem revisited

Cited in

(6)

• Online speedup learning for optimal planning
• Approximate dynamic programming using halfspace queries and multiscale Monge decomposition
• Online Dynamic Programming Speedups
• Theory and Applications of Models of Computation
• Computing a Hamiltonian path of minimum Euclidean length inside a simple polygon
• A new effective dynamic program for an investment optimization problem

This page was built for publication: Online dynamic programming speedups

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