English (United Kingdom)

https://curated-unify.zendy.io/wp-json/zendy-region/v1/featured_content/oa?rat=en

https://curated-unify.zendy.io/wp-json/zendy-region/v1/highlighted_journal/

Global: Zendy Plus annual

Presents the access of premium content as premium feature

Premium Content

Presents the keyphrase highlighting as premium feature

Keyphrase Highlighting

Presents the summarisation as premium feature

Summarisation

Insights

Presents the pdf analysis as premium feature

PDF Analysis

Presents the zaia usage as premium feature

ZAIA

Global: Zendy Plus monthly

Global: Zendy Tools annual

Global: Zendy Tools monthly

Global: Zendy Free Plan

Weitzman introduced Pandora's box problem as a mathematical model ofsequential search with inspection costs, in which a searcher is allowed toselect a prize from one of $n$ alternatives. Several decades later, Dovalintroduced a close version of the problem, where the searcher does not need toincur the inspection cost of an alternative, and can select it uninspected.Unlike the original problem, the optimal solution to the nonobligatoryinspection 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 differentpre-determined orders of inspection, and transitions from one to the other atmost 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 showPandora's problem with nonobligatory inspection belongs to class NP, which byusing the hardness result of [FLL22], settles the computational complexityclass of the problem. Finally, we provide a tight 0.8 approximation and a novelproof for committing policies [BK19] (informally, the set of nonadaptivepolicies) for general classes of distributions, which was previously shown onlyfor discrete and finite distributions [GMS08].

Pandora's Problem with Nonobligatory Inspection: Optimal Structure and a PTAS