Fully Polynomial Time Approximation Schemes for stochastic dynamic programs

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

*Corresponding author for this work

Research output: Chapter in Book/Report/Conference proceedingConference contribution

20 Scopus citations

Abstract

We develop a framework for obtaining (deterministic) Fully Polynomial Time Approximation Schemes (FPTASs) for stochastic univariate dynamic programs with either convex or monotone single-period cost functions. Using our framework, we give the first FPTASs for several NP-hard problems in various fields of research such as knapsack-related problems, logistics, operations management, economics, and mathematical finance.

Original languageEnglish (US)
Title of host publicationProceedings of the 19th Annual ACM-SIAM Symposium on Discrete Algorithms
Pages700-709
Number of pages10
StatePublished - Dec 1 2008
Event19th Annual ACM-SIAM Symposium on Discrete Algorithms - San Francisco, CA, United States
Duration: Jan 20 2008Jan 22 2008

Publication series

NameProceedings of the Annual ACM-SIAM Symposium on Discrete Algorithms

Other

Other19th Annual ACM-SIAM Symposium on Discrete Algorithms
CountryUnited States
CitySan Francisco, CA
Period1/20/081/22/08

ASJC Scopus subject areas

  • Software
  • Mathematics(all)

Fingerprint Dive into the research topics of 'Fully Polynomial Time Approximation Schemes for stochastic dynamic programs'. Together they form a unique fingerprint.

  • Cite this

    Halman, N., Klabjan, D., Li, C. L., Orlin, J., & Simchi-Levi, D. (2008). Fully Polynomial Time Approximation Schemes for stochastic dynamic programs. In Proceedings of the 19th Annual ACM-SIAM Symposium on Discrete Algorithms (pp. 700-709). (Proceedings of the Annual ACM-SIAM Symposium on Discrete Algorithms).