Pandora Box Problem with Nonobligatory Inspection: Hardness and Approximation Scheme

07/19/2022
by   Hu Fu, et al.
0

Weitzman (1979) introduced the Pandora Box problem as a model for sequential search with inspection costs, and gave an elegant index-based policy that attains provably optimal expected payoff. In various scenarios, the searching agent may select an option without making a costly inspection. The variant of the Pandora box problem with non-obligatory inspection has attracted interest from both economics and algorithms researchers. Various simple algorithms have proved suboptimal, with the best known 0.8-approximation algorithm due to Guha et al. (2008). No hardness result for the problem was known. In this work, we show that it is NP-hard to compute an optimal policy for Pandora's problem with nonobligatory inspection. We also give a polynomial-time approximation scheme (PTAS) that computes policies with an expected payoff at least (1 - ϵ)-fraction of the optimal, for arbitrarily small ϵ > 0. On the side, we show the decision version of the problem to be in NP.

READ FULL TEXT

Please sign up or login with your details

Forgot password? Click here to reset