Vol 5 No 2 (2010)
Articles

Speeding up Stochastic Dynamic Programming with Zero-Delay Convolution

Brian C. Dean
Clemson University
Published December 2, 2010
Keywords
  • dynamic programming,
  • stochastic dynamic programming,
  • convolution
How to Cite
Dean, B. C. (2010). Speeding up Stochastic Dynamic Programming with Zero-Delay Convolution. Algorithmic Operations Research, 5(2), Pages 96 - 104. Retrieved from https://journals.lib.unb.ca/index.php/AOR/article/view/12631

Abstract

We show how a technique from signal processing known as zero-delay convolution can be used to develop more efficient dynamic programming algorithms for a broad class of stochastic optimization problems. This class includes several variants of discrete stochastic shortest path, scheduling, and knapsack problems, all of which involve making a series of decisions over time that have stochastic consequences in terms of the temporal delay between successive decisions. We also correct a flaw in the original analysis of the zero-delay convolution algorithm.