Title: Approximation Algorithms for Stochastic Problems 

Speaker: R. Ravi
Carnegie Mellon University

Date: Thursday, August 25, 2005
Time 11-12 Venue: Room 3464 , HKUST   


Abstract 
Two-stage stochastic programming with recourse is an attempt to
model data uncertainty. Data for the current time (e.g. current
costs) are known, whereas the uncertain future is characterized by
a given probability distribution. After a set of decisions are
made in a first stage, the actual future is revealed (according to
the probability distribution). The first-stage solution can then
be augmented in a second recourse stage to obtain a feasible
solution for the realized scenario. The goal is to minimize the
sum of first-stage costs plus the expected costs in the second
stage.


We consider several classical combinatorial optimization problems
in this framework, and provide approximation algorithms for them.
In the talk, we will focus on a canonical problem in network
design - Steiner trees. Our approximation algorithm is based on a
simple boosted sampling idea.

This talk describes joint work with Anupam Gupta and Amitabh
Sinha, both from CMU.