Pandora's Box problem with order constraints

The Pandora's Box Problem, originally formalized by Weitzman in 1979, models selection from a set of options each with stochastic parameters, when evaluation (i.e. sampling) is costly. This includes, for example, the problem of hiring a skilled worker, where only one hire can be made, but the evaluation of each candidate is an expensive procedure. Weitzman showed that the Pandora's Box Problem admits a simple and elegant solution which considers the options in decreasing order of the value it which opening has exactly zero marginal revenue. We study for the first time this problem when the order in which the boxes are opened is constrained, which forces the threshold values to account for both the depth of search, as opening a box gives access to more boxes, and breadth, as there are many directions to explore in. Despite these difficulties, we show that greedy optimal strategies exist and can be efficiently computed for tree-like order constraints. We also prove that finding approximately optimal adaptive search strategies is NP-hard when certain matroid constraints are used to further restrict the set of boxes which may be opened, or when the order constraints are given as reachability constraints on a DAG. We complement the above result by giving approximate adaptive search strategies based on a connection between optimal adaptive strategies and non-adaptive strategies with bounded adaptivity gap for a carefully relaxed version of the problem.