  Weitzman introduced Pandora's box problem as a mathematical model of
sequential search with inspection costs, in which a searcher is allowed to
select a prize from one of $n$ alternatives. Several decades later, Doval
introduced a close version of the problem, where the searcher does not need to
incur the inspection cost of an alternative, and can select it uninspected.
Unlike the original problem, the optimal solution to the nonobligatory
inspection variant is proved to need adaptivity, and by recent work of [FLL22],
finding the optimal solution is NP-hard.
  Our first main result is a structural characterization of the optimal policy:
We show there exists an optimal policy that follows only two different
pre-determined orders of inspection, and transitions from one to the other at
most once. Our second main result is a polynomial time approximation scheme
(PTAS). Our proof involves a novel reduction to a framework developed by
[FLX18], utilizing our optimal two-phase structure. Furthermore, we show
Pandora's problem with nonobligatory inspection belongs to class NP, which by
using the hardness result of [FLL22], settles the computational complexity
class of the problem. Finally, we provide a tight 0.8 approximation and a novel
proof for committing policies [BK19] (informally, the set of nonadaptive
policies) for general classes of distributions, which was previously shown only
for discrete and finite distributions [GMS08].
