[Colloquium] TTIC Colloquium: Anupam Gupta, CMU
Liv Leader
lleader at ttic.edu
Mon Nov 14 09:44:42 CST 2011
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 <jam at ttic.edu>
Web- www.ttic.edu
<http://www.ttic.edu/>
-------------- next part --------------
An HTML attachment was scrubbed...
URL: http://mailman.cs.uchicago.edu/pipermail/colloquium/attachments/20111114/333f4640/attachment.htm
More information about the Colloquium
mailing list