| |
|
| |
|
Anupam Gupta
CMU
Approximation Algorithms for Stochastic Optimization
March 21, 2006 10:00am
Abstract:
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.
If you have questions, or would like to meet the speaker, please contact Ponda at 4-1994 or pondabarnes@tti-c.org. For information on future TTI-C talks or events, please go to the TTI-C Events page.