What About Wednesday? Approximation Algorithms for Multistage Stochastic Optimization

We study the problem of multi-stage stochastic optimization with recourse, and provide approximation algorithms using cost-sharing functions for such problems. Our algorithms use and extend the Boosted Sampling framework of [6]. We also show how the framework can be adapted to give approximation algorithms even when the inflation parameters are correlated with the scenarios