Online dynamic programming speedups

DOI10.1007/S00224-009-9166-XzbMATH Open1170.90512OpenAlexW2046367228MaRDI QIDQ839641FDOQ839641

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

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

zbMATH Keywords

dynamic programmingMonge property

Mathematics Subject Classification ID

Dynamic programming (90C39)

Cites Work

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

Cited In (5)

• Theory and Applications of Models of Computation
• Computing a Hamiltonian path of minimum Euclidean length inside a simple polygon
• Online speedup learning for optimal planning
• Online Dynamic Programming Speedups
• 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)