2026-07-26T03:20:12Z https://drops.dagstuhl.de/oai

oai:drops-oai.dagstuhl.de:18851 2024-03-06T11:02:44Z ddc:004 open_access

Approximating Pandora’s Box with Correlations Chawla, Shuchi Gergatsouli, Evangelia McMahan, Jeremy Tzamos, Christos Pandora’s Box Min Sum Set Cover stochastic optimization approximation preserving reduction We revisit the classic Pandora’s Box (PB) problem under correlated distributions on the box values. Recent work of [Shuchi Chawla et al., 2020] obtained constant approximate algorithms for a restricted class of policies for the problem that visit boxes in a fixed order. In this work, we study the complexity of approximating the optimal policy which may adaptively choose which box to visit next based on the values seen so far. Our main result establishes an approximation-preserving equivalence of PB to the well studied Uniform Decision Tree (UDT) problem from stochastic optimization and a variant of the Min-Sum Set Cover (MSSC_f) problem. For distributions of support m, UDT admits a log m approximation, and while a constant factor approximation in polynomial time is a long-standing open problem, constant factor approximations are achievable in subexponential time [Ray Li et al., 2020]. Our main result implies that the same properties hold for PB and MSSC_f. We also study the case where the distribution over values is given more succinctly as a mixture of m product distributions. This problem is again related to a noisy variant of the Optimal Decision Tree which is significantly more challenging. We give a constant-factor approximation that runs in time n^Õ(m²/ε²) when the mixture components on every box are either identical or separated in TV distance by ε. Schloss Dagstuhl – Leibniz-Zentrum für Informatik Shuchi Chawla and Evangelia Gergatsouli and Jeremy McMahan and Christos Tzamos 2023 Is Part Of LIPIcs, Volume 275, Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2023) InProceedings Text doc-type:ResearchArticle publishedVersion application/pdf doi:10.4230/LIPIcs.APPROX/RANDOM.2023.26 urn:nbn:de:0030-drops-188519 https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.APPROX/RANDOM.2023.26 eng https://creativecommons.org/licenses/by/4.0/legalcode