Provably Near-Optimal Approximation Schemes for Implicit Stochastic and Sample-Based Dynamic Programs

DOI10.1287/ijoc.2019.0926OpenAlexW2561934540MaRDI QIDQ5148198

Nir Halman

Publication date: 1 February 2021

Published in: INFORMS Journal on Computing (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1287/ijoc.2019.0926

zbMATH Keywords

inventory controlapproximation algorithmssample average approximation\(k\)-approximation sets and functions

Mathematics Subject Classification ID

Mathematical programming (90Cxx)

Related Items (3)

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
• The newsvendor problem: review and directions for future research
• A sparse sampling algorithm for near-optimal planning in large Markov decision processes
• Approximating convex functions via non-convex oracles under the relative noise model
• Approximation schemes for a class of subset selection problems
• The Data-Driven Newsvendor Problem: New Bounds and Insights
• The Logic of Logistics
• Approximating the Nonlinear Newsvendor and Single-Item Stochastic Lot-Sizing Problems When Data Is Given by an Oracle
• A Fully Polynomial-Time Approximation Scheme for Single-Item Stochastic Inventory Control with Discrete Demand
• An approximation scheme for stochastic linear programming and its application to stochastic integer programs
• When Does a Dynamic Programming Formulation Guarantee the Existence of a Fully Polynomial Time Approximation Scheme (FPTAS)?
• Sampling-Based Approximation Schemes for Capacitated Stochastic Inventory Control Models
• Fully Polynomial Time Approximation Schemes for Stochastic Dynamic Programs
• A General Framework for Designing Approximation Schemes for Combinatorial Optimization Problems with Many Objectives Combined into One
• Provably Near-Optimal Sampling-Based Policies for Stochastic Inventory Control Models
• Optimal Inventory Policy
• A Computationally Efficient FPTAS for Convex Stochastic Dynamic Programs
• Combinatorial methods in density estimation

This page was built for publication: Provably Near-Optimal Approximation Schemes for Implicit Stochastic and Sample-Based Dynamic Programs