Online Dynamic Programming Speedups

DOI10.1007/11970125_4MaRDI QIDQ5443508zbMATH OpenOpenAlexFDO

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

Publication date 21 February 2008

Published in Approximation and Online Algorithms (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1007/11970125_4

Mathematics Subject Classification ID

Analysis of algorithms (68W40) Dynamic programming (90C39) Computational methods for problems pertaining to operations research and mathematical programming (90-08)

Recommendations

• Online dynamic programming speedups
• The Knuth-Yao quadrangle-inequality speedup is a consequence of total monotonicity
• Online maintenance of k-medians and k-covers on a line
• Algorithm Theory - SWAT 2004
• On an efficient dynamic programming technique of F. F. Yao

Cited in

(9)

• Theory and Applications of Models of Computation
• Algorithm Theory - SWAT 2004
• Monge strikes again: Optimal placement of web proxies in the internet
• Approximate dynamic programming using halfspace queries and multiscale Monge decomposition
• Online speedup learning for optimal planning
• Sorting can exponentially speed up pure dynamic programming
• On-the-fly algorithms and sequential machines
• Online dynamic programming speedups
• On-the-Fly Algorithms and Sequential Machines

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 Q5443508)