Fully Polynomial Time Approximation Schemes for stochastic dynamic programs

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

Research output: Chapter in book / Conference proceedingConference article published in proceeding or bookAcademic researchpeer-review

20 Citations (Scopus)

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
Title of host publicationProceedings of the 19th Annual ACM-SIAM Symposium on Discrete Algorithms
Pages700-709
Number of pages10
Publication statusPublished - 1 Dec 2008
Event19th Annual ACM-SIAM Symposium on Discrete Algorithms - San Francisco, CA, United States
Duration: 20 Jan 200822 Jan 2008

Conference

Conference19th Annual ACM-SIAM Symposium on Discrete Algorithms
CountryUnited States
CitySan Francisco, CA
Period20/01/0822/01/08

ASJC Scopus subject areas

  • Software
  • Mathematics(all)

Cite this