论文标题
潘多拉盒子问题非渗透检查：硬度和近似方案
Pandora Box Problem with Nonobligatory Inspection: Hardness and Approximation Scheme
论文作者
论文摘要
Weitzman（1979）引入了Pandora Box问题，作为进行顺序搜索的模型，并提供了一项优雅的基于指数的政策，该政策可证明是最佳的预期收益。在各种情况下，搜索代理可以在不进行昂贵检查的情况下选择一个选项。潘多拉盒子问题的变体与非掩饰检查有关，引起了经济学和算法研究人员的兴趣。各种简单的算法已证明是次优的，其最著名的0.8-鉴定算法是Guha等。 （2008）。该问题尚无硬度结果。 在这项工作中，我们表明，计算潘多拉（Pandora）问题的最佳策略是NP-HARD。我们还提供了一个多项式时间近似方案（PTA），该方案计算具有预期收益至少$（1-ε）$的策略的最佳分数，用于任意的小$ε> 0 $。在侧面，我们显示了要在NP中的问题的决策版本。
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.
