Toward Breaking the Curse of Dimensionality: An FPTAS for Stochastic Dynamic Programs with Multidimensional Actions and Scalar States

DOI10.1137/18M1208423zbMath1411.90296arXiv1811.11680MaRDI QIDQ4634100

Giacomo Nannicini, Nir Halman

Publication date: 7 May 2019

Published in: SIAM Journal on Optimization (Search for Journal in Brave)

Full work available at URL: https://arxiv.org/abs/1811.11680

zbMATH Keywords

dynamic programmingapproximation algorithmsfully polynomial-time approximation schememultistage linear programming

Mathematics Subject Classification ID

Approximation methods and heuristics in mathematical programming (90C59) Combinatorial optimization (90C27) Dynamic programming (90C39)

Related Items (4)

Toward Breaking the Curse of Dimensionality: An FPTAS for Stochastic Dynamic Programs with Multidimensional Actions and Scalar States ⋮ Strongly polynomial FPTASes for monotone dynamic programs ⋮ Fully polynomial time \((\Sigma,\Pi)\)-approximation schemes for continuous nonlinear newsvendor and continuous stochastic dynamic programs ⋮ Automatic Generation of FPTASes for Stochastic Monotone Dynamic Programs Made Easier

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• A deterministic fully polynomial time approximation scheme for counting integer knapsack solutions made easy
• A polynomial-time algorithm, based on Newton's method, for linear programming
• On the complexity of energy storage problems
• Approximating convex functions via non-convex oracles under the relative noise model
• A fully polynomial-time approximation scheme for approximating a sum of random variables
• Fully polynomial time \((\Sigma,\Pi)\)-approximation schemes for continuous nonlinear newsvendor and continuous stochastic dynamic programs
• SMART: A Stochastic Multiscale Model for the Analysis of Energy Resources, Technology, and Policy
• Introduction to Stochastic Programming
• Approximate Dynamic Programming
• Sampling-Based Approximation Algorithms for Multistage Stochastic Optimization
• A Fully Polynomial-Time Approximation Scheme for Single-Item Stochastic Inventory Control with Discrete Demand
• The Linear Programming Approach to Approximate Dynamic Programming
• Discrete Convex Analysis
• Toward Breaking the Curse of Dimensionality: An FPTAS for Stochastic Dynamic Programs with Multidimensional Actions and Scalar States
• Fixed-Dimensional Stochastic Dynamic Programs: An Approximation Scheme and an Inventory Application
• Fully Polynomial Time Approximation Schemes for Stochastic Dynamic Programs
• An Optimal Approximate Dynamic Programming Algorithm for Concave, Scalar Storage Problems With Vector-Valued Controls
• An FPTAS for #Knapsack and Related Counting Problems
• On Minimizing Nonseparable Functions Defined on the Integers with an Inventory Application
• A Computationally Efficient FPTAS for Convex Stochastic Dynamic Programs

This page was built for publication: Toward Breaking the Curse of Dimensionality: An FPTAS for Stochastic Dynamic Programs with Multidimensional Actions and Scalar States