Opening Pandora’s Box: the Correlated Case.

Abstract: Pandora’s Box models optimization problems where the input consists of stochastic random variables, but the uncertainty can be removed (i.e. reveal the exact value of a variable) by paying an extra price. Our goal is to maximize (or minimize) the price of the variable chosen minus (resp. plus) the cost we paid to learn the exact instantiations of the variables. All previous work on this class of problems assumes that different random variables in the input are distributed independently. Until recently nothing was known for the case of correlated input.

In this talk I will introduce Pandora’s Box problem and describe the first constant approximation algorithm for Pandora’s Box with correlated distributions. I will also briefly mention a newer, simpler algorithm that directly generalizes the independent case algorithm while also improving on the approximation factor.

This is based on joint work with Shuchi Chawla, Yifeng Teng, Christos Tzamos and Ruimin Zhang.

Posted on Apr 3, 2023 in ACGO, Seminars