Please use this identifier to cite or link to this item: http://hdl.handle.net/10397/8794
Title: Fully polynomial time approximation schemes for stochastic dynamic programs
Authors: Halman, N
Klabjan, D
Li, CL 
Orlin, J
Simchi Levi, D
Keywords: Fully polynomial time approximation schemes
K-approximation
Stochastic dynamic programming
Issue Date: 2014
Publisher: Society for Industrial and Applied Mathematics Publications
Source: SIAM Journal on discrete mathematics, 2014, v. 28, no. 4, p. 1725-1796 How to cite?
Journal: SIAM Journal on Discrete Mathematics 
Abstract: We present a framework for obtaining fully polynomial time approximation schemes (FPTASs) for stochastic univariate dynamic programs with either convex or monotone single-period cost functions. This framework is developed through the establishment of two sets of computational rules, namely, the calculus of K-approximation functions and the calculus of K-approximation sets. Using our framework, we provide the first FPTASs for several NP-hard problems in various fields of research such as knapsack models, logistics, operations management, economics, and mathematical finance. Extensions of our framework via the use of the newly established computational rules are also discussed.
URI: http://hdl.handle.net/10397/8794
ISSN: 0895-4801
DOI: 10.1137/130925153
Appears in Collections:Journal/Magazine Article

Access
View full-text via PolyU eLinks SFX Query
Show full item record

SCOPUSTM   
Citations

9
Last Week
1
Last month
0
Citations as of Nov 2, 2018

WEB OF SCIENCETM
Citations

7
Last Week
0
Last month
0
Citations as of Nov 15, 2018

Page view(s)

58
Last Week
1
Last month
Citations as of Nov 11, 2018

Google ScholarTM

Check

Altmetric


Items in DSpace are protected by copyright, with all rights reserved, unless otherwise indicated.