Algorithms and Complexity Seminar
Monday, October 30, 2006, 4-5:15pm in 32-G575.
Fully Polynomial Time Approximation Schemes for Convex and for
Monotone Stochastic Dynamic Programming
Nir Halman (MIT)
We develop a framework for obtaining a (deterministic) Fully Polynomial
Time Approximation Scheme (FPTAS) to stochastic univariate dynamic
programming with either convex or monotone single period cost function.
Using our framework, we give the first FPTAS for several NP-Hard
problems in various fields of research.
Joint work with Diego Klabjan, Chung-Lun Li, James Orlin and David
Simchi-Levi.
Host: Ronitt Rubinfeld
(The Algorithms
and Complexity Seminar series talks are usually held Mondays from
4-5:15pm in 32-G575.)