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)

Full work available at URL https://doi.org/10.1137/13094774X

zbMATH Keywords

approximation algorithmsdiscrete convexitydynamic programmingfully polynomial-time approximation schemeinventory control

Mathematics Subject Classification ID

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

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

(15)

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

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)