Optimization Online


Toward breaking the curse of dimensionality: an FPTAS for stochastic dynamic programs with multidimensional action and scalar state

Nir Halman (halman***at***huji.ac.il)
Giacomo Nannicini (nannicini***at***us.ibm.com)

Abstract: We propose a Fully Polynomial-Time Approximation Scheme (FPTAS) for stochastic dynamic programs with multidimensional action, scalar state, convex costs and linear state transition function. The action spaces are polyhedral and described by parametric linear programs. This type of problems 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. The FPTAS relies on the solution of polynomial-sized linear programs to recursively compute an approximation of the value function at each stage. Our paper enlarges the class of dynamic programs that admit an FPTAS by showing, under suitable conditions, how to deal with multidimensional action spaces and with vectors of continuous random variables with bounded support. These results bring us one step closer to overcoming the curse of dimensionality of dynamic programming.

Keywords: Dynamic programming, linear programming, K-approximation sets and functions, FPTAS, approximation scheme

Category 1: Combinatorial Optimization (Approximation Algorithms )

Category 2: Other Topics (Dynamic Programming )

Category 3: Applications -- OR and Management Sciences (Supply Chain Management )


Download: [PDF]

Entry Submitted: 07/14/2017
Entry Accepted: 07/14/2017
Entry Last Modified: 08/22/2018

Modify/Update this entry

  Visitors Authors More about us Links
  Subscribe, Unsubscribe
Digest Archive
Search, Browse the Repository


Coordinator's Board
Classification Scheme
Give us feedback
Optimization Journals, Sites, Societies
Mathematical Optimization Society