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.
Assignment
Tasks are here: [PDF].
Due: 28 Feb (please send pdf to Piotr).