Fully Polynomial Time Approximation Schemes for Stochastic Dynamic Programs

DOI10.1137/130925153zbMath1408.68078OpenAlexW1997261476WikidataQ59592258 ScholiaQ59592258MaRDI QIDQ5246083

Diego Klabjan, Nir Halman, David Simchi-Levi, Chung-Lun Li, James B. Orlin

Publication date: 17 April 2015

Published in: SIAM Journal on Discrete Mathematics (Search for Journal in Brave)

Full work available at URL: http://hdl.handle.net/1721.1/109135

zbMATH Keywords

stochastic dynamic programmingfully polynomial-time approximation schemes\(K\)-approximation

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Derivative-free methods and methods using generalized derivatives (90C56) Stochastic programming (90C15) Transportation, logistics and supply chain management (90B06) Approximation methods and heuristics in mathematical programming (90C59) Inventory, storage, reservoirs (90B05) Dynamic programming (90C39) Markov and semi-Markov decision processes (90C40) Approximation algorithms (68W25)

Related Items (20)

An FPTAS for two performance measures for the relocation scheduling problem subject to fixed processing sequences ⋮ A deterministic fully polynomial time approximation scheme for counting integer knapsack solutions made easy ⋮ Approximation schemes for non-separable non-linear Boolean programming problems under nested knapsack constraints ⋮ On the complexity of energy storage problems ⋮ Knapsack problems with position-dependent item weights or profits ⋮ Unnamed Item ⋮ A technical note: fully polynomial time approximation schemes for minimizing the makespan of deteriorating jobs with nonlinear processing times ⋮ The TV advertisements scheduling problem ⋮ Toward Breaking the Curse of Dimensionality: An FPTAS for Stochastic Dynamic Programs with Multidimensional Actions and Scalar States ⋮ Provably Near-Optimal Approximation Schemes for Implicit Stochastic and Sample-Based Dynamic Programs ⋮ A faster FPTAS for counting two-rowed contingency tables ⋮ Approximating convex functions via non-convex oracles under the relative noise model ⋮ Resource allocation in rooted trees subject to sum constraints and nonlinear cost functions ⋮ Bi-criteria path problem with minimum length and maximum survival probability ⋮ Sampling-Based Approximation Schemes for Capacitated Stochastic Inventory Control Models ⋮ A review of four decades of time-dependent scheduling: main results, new topics, and open problems ⋮ Strongly polynomial FPTASes for monotone dynamic programs ⋮ Fully polynomial time \((\Sigma,\Pi)\)-approximation schemes for continuous nonlinear newsvendor and continuous stochastic dynamic programs ⋮ Robust inventory problem with budgeted cumulative demand uncertainty ⋮ Automatic Generation of FPTASes for Stochastic Monotone Dynamic Programs Made Easier

This page was built for publication: Fully Polynomial Time Approximation Schemes for Stochastic Dynamic Programs