CS&E Seminar: Anupam Gupta - Approximation Algorithms for Stochastic Combinatorial Optimization - February 21, 2012, at 12:00 @Aula Magna
Speaker: Anupam Gupta, Carnegie Mellon University, U.S.A.
Title: Approximation Algorithms for Stochastic Combinatorial Optimization
Time and Location: Tuesday, February 21, 2012, at 12:00, Aula Magna
Abstract: 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.
Contacts: Domenico Lembo, Massimo Mecella, Stefano Leonardi
Computer Science & Engineering seminar series web page: www.dis.uniroma1.it/~seminf