A computationally efficient FPTAS for convex stochastic dynamic programs

DOI10.1137/13094774XMaRDI QIDQ5892239zbMATH OpenWikidataFDO

Authors Nir Halman, Giacomo Nannicini, James B. Orlin

Publication date 13 January 2017

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

zbMATH Keywords

dynamic programmingapproximation algorithmsinventory controldiscrete convexityfully polynomial-time approximation scheme

Mathematics Subject Classification ID

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

Recommendations

• A Computationally Efficient FPTAS for Convex Stochastic Dynamic Programs
• Fully polynomial time approximation schemes for stochastic dynamic programs
• Toward breaking the curse of dimensionality: an FPTAS for stochastic dynamic programs with multidimensional actions and scalar states
• Fully polynomial time (,)-approximation schemes for continuous nonlinear newsvendor and continuous stochastic dynamic programs
• Fixed-dimensional stochastic dynamic programs: an approximation scheme and an inventory application

Cited in

(13)

• A faster FPTAS for counting two-rowed contingency tables
• A Computationally Efficient FPTAS for Convex Stochastic Dynamic Programs
• The TV advertisements scheduling problem
• Single machine scheduling with assignable due dates to minimize maximum and total late work
• Fixed-dimensional stochastic dynamic programs: an approximation scheme and an inventory application
• Knapsack problem with objective value gaps
• Provably Near-Optimal Approximation Schemes for Implicit Stochastic and Sample-Based Dynamic Programs
• On the complexity of energy storage problems
• Fully polynomial time approximation schemes for stochastic dynamic programs
• A PTAS for a class of stochastic dynamic programs
• Fully polynomial time (,)-approximation schemes for continuous nonlinear newsvendor and continuous stochastic dynamic programs
• Toward breaking the curse of dimensionality: an FPTAS for stochastic dynamic programs with multidimensional actions and scalar states
• When Does a Dynamic Programming Formulation Guarantee the Existence of a Fully Polynomial Time Approximation Scheme (FPTAS)?

This page was built for publication: A computationally efficient FPTAS for convex stochastic dynamic programs

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q5892239)