CSAIL Event Calendar: Previous Series

Fully Polynomial Time Approximation Schemes for Convex and for Monotone Stochastic Dynamic Programming

Speaker: Nir Halman , MIT
Date: October 30 2006
Time: 4:00PM to 5:15PM
Location: 32-G575
Host: Ronitt Rubinfeld, MIT CSAIL

Contact: Joanne Hanley, 617.253.6054, joanne@csail.mit.edu
Relevant URL: http://theory.csail.mit.edu/~madhu/algcomp/nir-abs.html

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.

See other events that are part of Algorithms and Complexity Series 2006/2007

See other events happening in October 2006