  The Pandora's Box problem models the search for the best alternative when
evaluation is costly. In its simplest variant, a decision maker is presented
with $n$ boxes, each associated with a cost of inspection and a distribution
over the reward hidden within. The decision maker inspects a subset of these
boxes one after the other, in a possibly adaptive ordering, and obtains as
utility the difference between the largest reward uncovered and the sum of the
inspection costs. While this classic version of the problem is well understood
(Weitzman 1979), recent years have seen a flourishing of the literature on
variants of the problem. In this paper, we introduce a general framework -- the
Pandora's Box Over Time problem -- that captures a wide range of variants where
time plays a role, e.g., as it might constrain the schedules of exploration and
influence both costs and rewards. In the Pandora's Box Over Time problem, each
box is characterized by time-dependent rewards and costs, and inspecting it
might require a box-specific processing time. Moreover, once a box is
inspected, its reward may deteriorate over time, possibly differently for each
box. Our main result is an efficient $21.3$-approximation to the optimal
strategy, which is NP-hard to compute in general. We further obtain improved
results for the natural special cases where boxes have no processing time, or
when costs and reward distributions do not depend on time (but rewards may
deteriorate after inspecting).
