Fully polynomial-time approximation schemes for stochastic dynamic programs: theory and applications
Abstract
This talk presents some recent results in our quest to build approximation algorithms for stochastic dynamic programs that are both theoretically and computationally efficient. The main constructive result is an FPTAS for dynamic programs with scalar state, polyhedral action spaces, convex costs, and linear transition functions. The random variables are assumed to be described compactly by an oracle to their CDFs. This type of problem finds applications in the area of optimal planning under uncertainty and can be thought of as the problem of optimally managing a single non-discrete resource over a finite time horizon. We show that under a value oracle model for the cost functions, this result for one-dimensional state space is "best possible" because a similar dynamic programming model with two-dimensional state space does not admit a PTAS. Along the way, we will discuss hardness results regarding the inapproximability of certain two-dimensional convex functions and, if time permits, applications to a newsvendor model. The talk is based on joint work with Nir Halman.
