Fully Polynomial Time Approximation Schemes for Stochastic Dynamic Programs

COMPUTER SCIENCE/DISCRETE MATH I
Topic:Fully Polynomial Time Approximation Schemes for Stochastic Dynamic Programs
Speaker:Nir Halman
Affiliation:Massachusetts Institute of Technology
Date:Monday, April 16
Time/Room:11:15am - 12:15pm/S-101

We develop a framework for obtaining (deterministic) Fully Polynomial Time Approximation Schemes (FPTASs) for stochastic univariate dynamic problems 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 theoretical computer science, logistics, operational management, economics and finance. Joint work with Diego Klabjan, Chung-Lun Li, James Orlin and David Simchi-Levi.