Stochastic Optimization

We give a brief introduction to the area of stochastic optimization, describing some problems and techniques studied recently. We then focus on two algorithms -- a constant factor approximation for stochastic Steiner tree with recourse due to Gupta et al. [PS], and a constant factor approximation for a stochastic ruoting problem on planar graphs due to Roughgarden and myself [PDF].