Optimization Online


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

Nir Halman (halman***at***huji.ac.il)

Abstract: In this paper we address two models of non-deterministic discrete-time finite-horizon dynamic programs (DPs): implicit stochastic DPs the information about the random events is given by value oracles to their CDFs; and sample-based DPs the information about the random events is deduced via samples. In both models the single period cost functions are accessed via value oracle calls and are assumed to possess either monotone or convex structure. We develop the first near-optimal relative approximation schemes for each of the two models. Applications in stochastic inventory control, i.e., several variants of the so called Newsvendor problem are discussed in detail. Our results are achieved by a combination of Bellman equation calculations, density estimation results, and extensions of the technique of K- approximation sets and functions introduced by Halman et al. [Math. Oper. Res., 34, (2009), pp. 674685].

Keywords: Approximation algorithms, inventory control, $K$-approximation sets and functions, sample average approximation

Category 1: Other Topics (Dynamic Programming )

Citation: This paper has been acccepted for publication by Informs Journal on Computing and is available online at the author's personal webpage. Parts of this work were first presented in April 23rd 2014 in the annual meeting of the Israel OR society as "Approximation Schemes for Sample-Based Non-linear Newsvendor", see: http://ie.technion.ac.il/Labs/Orsis/kenes_2014/ORSIS_2014_program.pdf First full version appeared on June 8th 2015 under the title: "Provably Near-Optimal Approximation Schemes for Sample-Based Dynamic Programs with emphasis on stochastic inventory control models".


Entry Submitted: 06/08/2015
Entry Accepted: 06/08/2015
Entry Last Modified: 07/29/2019

Modify/Update this entry

  Visitors Authors More about us Links
  Subscribe, Unsubscribe
Digest Archive
Search, Browse the Repository


Coordinator's Board
Classification Scheme
Give us feedback
Optimization Journals, Sites, Societies
Mathematical Optimization Society