Stochastic Knapsack: Semi-Adaptivity Gaps and Improved Approximation

Zohar Barak, Inbal Talgam-Cohen

In stochastic combinatorial optimization, algorithms differ in their adaptivity: whether or not they query realized randomness and adapt to it. Dean et al. (FOCS '04) formalize the…