CSAIL Event Calendar: Previous Series
Approximation Algorithms for 2-Stage Stochastic Optimization Problems
Speaker: David Shmoys , Cornell University
Relevant URL: http://theory.lcs.mit.edu/theory-seminars/calendar.html
We will survey recent work in the design of approximation algorithms for the class of 2-stage stochastic optimization problems with recourse. These results have built on techniques initially developed in the context of deterministic approximation, including rounding approaches, primal-dual algorithms and analyses, as well as an elegant random sampling technique. Among the problems that we shall discuss are stochastic variants of the set covering problem (as well as the related uncapacitated facility location problem), the Steiner tree problem, and the problem of scheduling the maximum-weight set of on-time jobs.