A $1/2$-Approximation for Pandora's Problem with Deadlines

1 Introduction

• The algorithm directly combines Weitzman’s reservation-value idea with a threshold–surplus analysis, avoiding intermediate adaptivity-gap and submodular-maximization losses.The reservation-capped threshold surplus function bridges the deadline setting and the classical prophet inequality.Source: §1 · p. 2
• 1/2-approximation for Pandora’s problem with deadlines improves the previous guarantee, which was arbitrarily close to 1/4.The result is stated as Theorem 1.Source: §1 · p. 2
• Immediate commitment means accepting a box’s value or rejecting it irrevocably upon opening, and the 1/2 guarantee holds against a more permissive benchmark.The benchmark is fully adaptive and may defer commitment until stopping; the text also states that 1/2 is best possible for immediate-commitment algorithms against it.Source: §1 · p. 2
• Approximately 0.778 is the upper bound on the approximation ratio for partially adaptive algorithms relative to the fully adaptive optimum, even with uniform deadlines.Partial adaptivity fixes the boxes and opening order in advance while allowing stopping to depend on observed values; in the classical problem, Weitzman’s rule attains the fully adaptive optimum.Source: §1 · pp. 2–3

1.1 Other Related Work

• Related work covers constrained, correlated, temporal, and online variants of Pandora’s problem.Examples include the Price of Information framework [Singla, 2018], correlated values [Chawla et al., 2020, 2023, Gergatsouli and Tzamos, 2023, Bansal et al., 2025], and Pandora’s Box Problem Over Time [Amanatidis et al., 2024].Source: §1.1 · p. 3

2.1 Pandora’s Problem with Deadlines

• Boxes have independent nonnegative values drawn from known distributions, known opening costs and deadlines, and finite expected values.Opening a box reveals its value and incurs its cost; a strategy may open at most one box per round and commit to at most one opened box.Source: §2.1 · pp. 3–4
• Immediate commitment discards or accepts a box upon opening, while deferred rules preserve opened boxes until their deadline or until stopping.These rules become increasingly permissive, with immediate commitment the strongest restriction.Source: §2.1 · p. 4
• The algorithm is partially adaptive with immediate commitment, and its benchmark is fully adaptive with deferred-until-stopping commitment.The benchmark respects opening deadlines and may commit to a box after its deadline if that box was opened on time.Source: §2.1 · p. 4

2.2 Weitzman’s Rule

• Without deadlines, Weitzman’s rule is optimal under deferred commitment and opens boxes in reservation-value order, stopping when an observed value reaches the largest remaining reservation value.It then commits to the opened box with the highest realized value.Source: §2.2 · pp. 4–5
• Weitzman’s rule can have a ratio tending to zero against the optimal immediate-commitment strategy when deadlines make its opening order exclude a box.Opening box 1 first and committing immediately avoids the loss in the example.Source: §2.2 · p. 5
• Box 2’s rare high payoff gives it a slightly larger reservation value, so opening it first prevents opening box 1 after its deadline.Deferred-until-stopping commitment cannot recover an unopened box whose deadline has passed.Source: §2.2 · p. 5

3 Our Algorithm

• The reservation-capped threshold surplus directly connects reservation values with prophet-inequality threshold surplus, avoiding the prior framework’s adaptivity-gap and submodular-maximization losses.The prior reductions yielded a guarantee arbitrarily close to 1/4.Source: §3 · p. 6

3.1 Reservation-capped Threshold Surplus

• For every threshold t, maximizing the feasible-set benchmark upper-bounds OPT; minimizing over t gives OPT ≤ min_t≥0 max_S∈D Bt(S).The benchmark is t plus the total reservation-capped surplus of a feasible set.Source: §3.1 · pp. 6, 8
• A set is deadline-feasible exactly when its jth box in deadline order has deadline at least j, and weighted maximization takes O(n^2) state transitions.Using weights wi(t) computes the maximum-surplus feasible set for a fixed threshold.Source: §3.1 · p. 8

3.2 Immediate Commitment via a Balanced Threshold

• At a threshold t* where W(t*) = t*, the algorithm selects a maximum-surplus feasible set and opens its positive-surplus boxes in deadline order, accepting the first value above t*.If no value exceeds the threshold, it accepts the last box; if there are no positive-surplus boxes, it stops without selecting one.Source: §3.2 · pp. 8–10
• The algorithm achieves a 1/2-approximation against the fully adaptive optimum with deferred-until-stopping commitment.It is partially adaptive and makes an immediate accept-or-reject decision after opening each box.Source: §3 · p. 5, §3.2 · p. 10
• For finite-support distributions, an LP with O(M + n^2) variables and constraints computes t* exactly and yields the exact 1/2 guarantee for rational binary-encoded inputs.The dynamic program at t* then recovers the maximizing feasible set.Source: §3.2 · pp. 10–11
• The 1/2 factor is optimal among immediate-commitment policies, even fully adaptive ones, against the best partially adaptive strategy with deferred-until-stopping commitment.A two-box example makes the ratio approach 1/2.Source: §3.2 · p. 11

4 Hardness of Partial Adaptivity

• On some instance, OPTPA(I) < 0.778 · OPTFA(I), so partial adaptivity cannot guarantee a worst-case ratio above 0.778 against full adaptivity.The bound holds even with unlimited computational power.Source: §4 · p. 11
• The witness has at least k boxes of each type, zero opening costs, deadline k for every box, and at most k boxes can be opened.The values are mutually independent, and the utility is the largest opened value.Source: §4 · p. 11
• A partially adaptive policy fixes its opening order, whereas the feasible fully adaptive policy opens type-1 boxes until success and then uses remaining rounds on type-2 boxes.The fully adaptive policy need not be optimal for the argument.Source: §4 · p. 12

• The algorithm achieves 1/2 against the fully adaptive, deferred-until-stopping optimum; immediate-commitment policies cannot improve that ratio, and partial adaptivity is capped at 0.778 under deferred commitment.Source: §5 · p. 13
• Deferred-to-deadline commitment would let policies gather observations while retaining earlier unexpired boxes for selection, but neither this nor prior algorithms exploits that flexibility.Source: §5 · p. 13
• The conclusion asks whether efficient fully adaptive opening orders can outperform partial adaptivity under deferred commitment, noting that deadlines make partial adaptivity strictly weaker.Source: §5 · p. 13

• The authors developed the theoretical results without AI assistance, then used ChatGPT Astra to proofread and polish the manuscript, reviewed its presentation, and took responsibility for its content.Source: Declaration of AI Usage · p. 13