We consider the following version of the Steiner Tree problem: on Monday (the first stage), we are
given a graph and are allowed to buy edges at unit cost. However, instead of a set of terminals (as
is usual), we are given a probability distribution D on subsets of vertices. (Let E_1 be the edges
bought in this first stage.) Subsequently, on Tuesday, we are given the actual set of terminals T
drawn from the distribution D, and must now augment our first stage solution E_1 with more edges to
obtain a feasible solution for this set T of terminals. However, the cost of edges bought in this
second stage is possibly higher than in the first stage. The goal is to minimize the expectated cost
incurred, where the expectation is over the uncertainty in the world (the distribution D) as well as
our coin tosses (if our algorithm is randomized). This framework is called "two-stage stochastic
optimization with recourse": clearly, one can consider many optimization problems in this model.

In this talk, we will outline a general technique to obtain approximation algorithms for this
stochastic problem from approximation algorithms for the non-stochastic Steiner tree problem: the
ideas we will develop are fairly general, and can be used for other classical combinatorial
optimization problems like facility location and vertex cover as well. We will talk about how our
results can be extended to multiple stages of decision-making, and indicate future directions.

This is based on work with Martin Pal, R. Ravi, and Amitabh Sinha.