Approximation algorithms for stochastic optimization problems

Lecturer: Prof. Piotr Sankowski (University of Warsaw).

About the lecturers | Course Summary | Slides | Assignment

About the lecturer: Piotr Sankowski received a M.Sc. degree in Computer Science in 2002 and a Ph.D. degree in Computer Science in 2005, both from the Warsaw University, Poland. Later, he became an associate professor at the Warsaw University. From September 2006 to April 2008 he is a post-doc fellow at "Sapienza" the University of Rome, Italy. Moreover, he received a M.Sc. degree in Physics in 2003 from the Warsaw University and is perusing his Ph.D. studies in Physics at Polish Academy of Sciences. He has received the ESA'04, FOCS'04, ESA'05 Best Student Paper Awards and is the winner of Witold Lipski prize for Young Researchers in Computer Science.

Course summary:
One of the recent developments in the field of approximation algorithms for discrete optimization problems was the creation of efficient algorithms for the stochastic version of the problems. During the lectures I will introduce the stochastic models, i.e., 2-stage stochastic optimization problems with recourse, online stochastic problems, and universal stochastic problems. The results for stochastic problems are build upon the techniques developed for deterministic algorithms, e.g., LR rounding, primal dual-algorithms, and random sampling technique. One of the tool problems is the stochastic Steiner tree problem that will be used during the lecture to present different ideas. Latter on, we will move on to the stochastic set cover problem that builds on more advanced techniques.


Tasks are here: [PDF]. Due: 28 Feb (please send pdf to Piotr).