Upcoming Events
INDUSTRIAL AND SYSTEMS ENGINEERING SEMINAR SERIES
Title: Fully Polynomial-Time Approximation Schemes for Stochastic Dynamic Programs: Theory and Applications
Abstract
This talk presents some recent results in our quest to build approximation algorithms for stochastic dynamic programs that are both theoretically and computationally efficient. The main constructive result is an FPTAS for dynamic programs with scalar state, polyhedral action spaces, convex costs and linear transition functions. The random variables are assumed to be described compactly by an oracle to their CDFs. This type of problem finds applications in the area of optimal planning under uncertainty, and can be thought of as the problem of optimally managing a single non-discrete resource over a finite time horizon.
We show that under a value oracle model for the cost functions this result for one-dimensional state space is “best possible”, because a similar dynamic programming model with two-dimensional state space does not admit a PTAS. Along the way, we will discuss hardness results regarding the inapproximability of certain two-dimensional convex functions, and, if time permits, applications to a newsvendor model. The talk is based on joint work with Nir Halman.
Bio sketch
Giacomo Nannicini is a Research Staff Member in the Theory of Quantum Computing and Information group at the IBM T. J. Watson Research Center. Before joining IBM, he was an assistant professor in the Engineering Systems and Design pillar at the Singapore University of Technology and Design. His main research interest is optimization broadly defined and its applications. Giacomo received several awards, including the 2016 COIN-OR Cup, the 2015 Robert Faure prize, the 2012 Glover-Klingman prize. His algorithms and software are used by one of the largest real-time traffic and mobility information groups in Europe, and by IBM's Cloud AI service.
Past Events
Spring 2019