Approximating Pandora's Knapsack via Simple Policies

Zohar Barak, Asnat Berlin, Ilan Reuven Cohen +3

We introduce Pandora's Knapsack: a hybrid between the classic stochastic knapsack problem [Dean et al., 2008] and Pandora's box [Weitzman, 1979]. As in stochastic knapsack, items h…