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