Approximation algorithms for stochastic and risk-averse optimization
Title | Approximation algorithms for stochastic and risk-averse optimization |
Publication Type | Conference Papers |
Year of Publication | 2007 |
Authors | Srinivasan A |
Conference Name | Proceedings of the eighteenth annual ACM-SIAM symposium on Discrete algorithms |
Date Published | 2007/// |
Publisher | Society for Industrial and Applied Mathematics |
Conference Location | Philadelphia, PA, USA |
ISBN Number | 978-0-898716-24-5 |
Abstract | 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. |
URL | http://dl.acm.org/citation.cfm?id=1283383.1283523 |