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. See other events that are part of Theory Colloquium Fall 2006 |
