Title:  Stochastic Combinatorial Optimization: A Survey of Recent Results
Speaker: Man-Cho Anthony So
Stanford University

Date: Friday September 22, 2006
Time 3-4PM
Venue: Room 3584, HKUST

  
Abstract:
Due to their wide applicability and versatile modeling power,
stochastic programming problems have received a lot of attention in
many communities.  In particular, there has been substantial recent
interest in 2-stage stochastic combinatorial optimization
problems in the computer science community.  Two objectives have been 
considered in recent work: one sought to minimize the expected cost, 
and the other sought to minimize the worst-case cost.  In the first 
part of this talk, we will survey some of these recent developments.  
In the second part of the talk, we argue that the above two objectives 
represent two extremes in handling risk -- the first trusts the average, 
and the second is obsessed with the worst case.  We then interpolate 
between these two extremes by introducing an one-parameter family of 
functionals.  These functionals arise naturally from a change of the 
underlying probability measure and incorporate an intuitive notion of risk.  
Although such a family has been used in the mathematical finance 
(Rockafellar et al., J. Banking & Finance 2002) and stochastic programming 
(Ruszczynski et al., 2005) literature before, its use in the context of 
approximation algorithms seems new.  We show that under standard assumptions, 
our risk-adjusted objective can be efficiently treated by the Sample Average 
Approximation (SAA) method (Kleywegt et al., SIAM J. Opt. 2001)
In particular, our result generalizes a recent sampling theorem by
Charikar et al. (RANDOM 2005), and it shows that it is possible to
incorporate some degree of robustness even when the underlying probability 
distribution can only be accessed in a black-box fashion.  We also show that 
when combined with known techniques (e.g. Dhamdhere et al., FOCS 2005, 
Shmoys et al., FOCS 2004), our result yields new approximation
algorithms for many 2-stage stochastic combinatorial optimization
problems under the risk-adjusted setting.