| 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.