2017/12/18 by Jarosław Byrka, Aravind Srinivasan, Byrka, Jaroslaw +1 · 2 citations
Decision Sciences · Engineering · Mathematics · #68W20 #68W25 #90C15 #Advanced Optimization Algorithms Research #Data Structures and Algorithms (cs.DS) #FOS: Computer and information sciences #Optimization and Mathematical Programming #Risk and Portfolio Optimization
paper · pdf · doi:10.48550/arxiv.1712.06996
openalex publication_date 2017/12/18 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28
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 which shows an approximability that 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. We give a 2.2975-approximation algorithm in the standard polynomial-scenario model and an algorithm with an expected per-scenario 2.4957-approximation guarantee, which is applicable to the more general black-box distribution model.