Corelab Seminar

Haris Angelidakis
Approximation algorithms for 2-Stage Stochastic Optimization Problems

In this talk, we will continue our overview of the research done in the field of 2-stage Stochastic Optimization the last decade. We will focus on the work of David B. Shmoys and Chaitanya Swamy on 2-stage stochastic optimization problems, and more specifically on the papers “Stochastic Optimization is (almost) as easy as deterministic optimization” (FOCS 2004) and “The Sample Average Approximation Method for 2-stage Stochastic Optimization” (unpublished manuscript).

We will present an FPRAS for solving a wide class of 2-stage stochastic problems which can be used, in conjuction with rounding techniques, to yield constant factor approximation algorithms for various combinatorial problems. We will reach this result by utilizing two different methods, the ellipsoid method and the Sample Average Approximation Method (SAA). Both methods are widely used in various problems and present much interest, the first being used mostly for theoretical results, while the second for much more practical applications.