Speaker: Chadi Kari
Day:  Wednesday, 12/7/2005
Room: ITEB 201
Time: 3:30pm
Title: On the Cost and Benefits of Procrastination: Approximation
Algorithms for Stochastic Combinatorial Optimization Problems 

Abstract:
Combinatorial optimization is often used to plan ahead, purchasing and
allocating resources for needs that are not known at the time of the
solution. This advanced planning is useful because purchasing ressources
becomes expensive at the last minute when the exact demands are known. On
the other hand, the "wait and see" approach allows us to take advantage of
late arriving information. Often a tradeoff is needed. In this setting the
authors consider a number of combinatorial optimization problems, and show
how to approximately optimize the choice of what to purchase ahead and what
to defer.

Reference: 
On the Cost and Benefits of Procrastination: Approximation Algorithms for
Stochastic Combinatorial Optimization Problems (SODA 2004)

Nicole Immorlica, David Karger, Maria Minkoff, Vahab S. Mirrokni