Approximation algorithms for stochastic and risk-averse optimization

TitleApproximation algorithms for stochastic and risk-averse optimization
Publication TypeConference Papers
Year of Publication2007
AuthorsSrinivasan A
Conference NameProceedings of the eighteenth annual ACM-SIAM symposium on Discrete algorithms
Date Published2007///
PublisherSociety for Industrial and Applied Mathematics
Conference LocationPhiladelphia, PA, USA
ISBN Number978-0-898716-24-5

We present improved approximation algorithms in stochastic optimization. We prove that the multi-stage stochastic versions of covering integer programs (such as set cover and vertex cover) admit essentially the same approximation algorithms as their standard (non-stochastic) counterparts; this improves upon work of Swamy & Shmoys that shows an approximability which depends multiplicatively on the number of stages. We also present approximation algorithms for facility location and some of its variants in the 2-stage recourse model, improving on previous approximation guarantees.