Approximation Algorithms for Discrete Stochastic Optimization Problems

We will survey recent work in the design of approximation algorithms for several discrete stochastic optimization problems, with a particular focus on 2-stage problems with recourse. In each of the problems we discuss, we are given a probability distribution over inputs, and the aim is to find a feasible solution that minimizes the expected cost of the solution found (with respect to the input distribution); an approximation algorithm finds a solution that is guaranteed to be nearly optimal. Among the specific problems that we shall discuss are stochastic generalizations of the traditional deterministic facility location problem, a simple sin...