[Colloquium] TTIC Colloquium: Anupam Gupta, CMU

[Liv Leader]

REMINDER:

When:     Monday, November 21 @ 11 a.m.

Where:   TTIC Conference Room #526, 6045 S. Kenwood Avenue, 5th Floor

Who:      Anupam Gupta, CMU

Title:      Approximation Algorithms for Stochastic Combinatorial Optimization

Imagine you are dealing with online requests to build a network. But
the requests are not generated adversarially --- they are drawn from
a known probability distribution. Morally, you should be able to do
better than in the worst case: can you, though?

On the other hand, here's another problem. You're packing items into
a knapsack, but the sizes of the items are now drawn from a known
probability distribution (and you know the size only when you decide
to add it to the knapsack). Clearly, this time the stochastic problem
is only harder than the usual case when the sizes are all fixed. Can
you do (almost) as well as the deterministic case?

These are just two of the problems that have been studied recently, in
the general setting of approximation algorithms for stochastic problems.
In this talk I'll try to give an overview of some results and ideas that
have come out of this research.

Host: Julia Chuzhoy, cjulia at ttic.edu


-- 
Liv Leader
Human Resources Coordinator

Toyota Technological Institute Chicago
6045 S Kenwood Ave
Chicago, IL 60637
Phone- (773) 702-5033
Fax-     (773) 834-9881
Email-  lleader at ttic.edu
Web-   www.ttic.edu