Speeding up Stochastic Dynamic Programming with Zero-Delay Convolution

Authors

  • Brian C. Dean Clemson University

Keywords:

dynamic programming, stochastic dynamic programming, convolution

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.

Downloads

Published

2010-12-02

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

Issue

Vol. 5 No. 2 (2010)

Section

Articles

License

The copyright of the submitted article is hereby transferred to “Preeminent Academic Facets Inc. (the “publisher”) to the extent possible by the laws in the respective countries of the author(s). The author(s) retain all other rights including the following: 1. Any patents and trademark rights. 2. Right to post a pre-print version of the paper on the author’s personal website which is not used for commercial purposes. The author(s) warrant that the work is original, it has not been published elsewhere, it is not currently under consideration for publication in any form, and it does not infringe any copyright laws. The signing author or agent further warrants that all authors, if applicable, have been informed of the terms of this agreement and obtained the approval and authority to sign the agreement.