dus_approx_of_pos_opt
theoremverified
If a constant factor approximation ratio c is achieved by partially adaptive policies on all instances with optDUS > 0, then it is achieved on all instances.
Statement
theorem dus_approx_of_pos_opt (c : ℝ)
(h_pos : ∀ inst : PandoraDeadlineInstance, 0 < optDUS inst →
∃ π : AdaptivePolicy inst.n, IsValidPolicy inst π ∧ IsPartiallyAdaptive π ∧
c * optDUS inst ≤ expectedUtilityDUS inst π)
(inst : PandoraDeadlineInstance) :
∃ π : AdaptivePolicy inst.n, IsValidPolicy inst π ∧ IsPartiallyAdaptive π ∧
c * optDUS inst ≤ expectedUtilityDUS inst π- Source
- step towards op184_partially_adaptive_beyond_half
- Verified
- 26 Oct 2026
- Axioms
Classical.choiceQuot.soundpropext- Built on 10
- opt_dus_nonnegFor any Pandora deadline instance
inst,0 ≤ optDUS inst. - is_valid_policy_stopFor every Pandora's problem instance with deadlines
inst : PandoraDeadlineInstance, the policyAdaptivePolicy.stopsatisfies… - is_partially_adaptive_stopFor any natural number
n, the policyAdaptivePolicy.stop : AdaptivePolicy nis partially adaptive (… - expected_utility_dus_stopFor any Pandora deadline instance
inst, the expected net utilityexpectedUtilityDUS inst AdaptivePolicy.stopis zero. - PandoraDeadlineInstanceAn instance of Pandora's problem with deadlines consisting of n boxes, each with a non-negative opening cost, a positive integer deadline,…
- IsValidPolicyA policy is valid for a Pandora's problem instance with deadlines if it respects opening deadlines and never opens any box more than once.
- AdaptivePolicyA fully adaptive search policy for Pandora's problem with n boxes, represented as a decision tree that at each step either stops or opens…
- IsPartiallyAdaptiveA search policy
π : AdaptivePolicy nfor Pandora's problem is partially adaptive if there exists a predetermined ordered list of boxes… - optDUSThe optimal expected net utility
optDUS instunder deferred-until-stopping commitment for a Pandora's problem instance with deadlines… - expectedUtilityDUSThe expected net utility of an adaptive policy
π : AdaptivePolicy inst.nunder deferred-until-stopping commitment on a Pandora's problem…
- opt_dus_nonnegFor any Pandora deadline instance
Lean source view module on GitHub
/-- Reduction of approximation ratio guarantee to instances with strictly positive optDUS. -/ theorem dus_approx_of_pos_opt (c : ℝ) (h_pos : ∀ inst : PandoraDeadlineInstance, 0 < optDUS inst → ∃ π : AdaptivePolicy inst.n, IsValidPolicy inst π ∧ IsPartiallyAdaptive π ∧ c * optDUS inst ≤ expectedUtilityDUS inst π) (inst : PandoraDeadlineInstance) : ∃ π : AdaptivePolicy inst.n, IsValidPolicy inst π ∧ IsPartiallyAdaptive π ∧ c * optDUS inst ≤ expectedUtilityDUS inst π := by by_cases h : 0 < optDUS inst · exact h_pos inst h · have h0 : optDUS inst = 0 := by have := opt_dus_nonneg inst linarith use AdaptivePolicy.stop refine ⟨is_valid_policy_stop inst, is_partially_adaptive_stop inst.n, ?_⟩ rw [expected_utility_dus_stop, h0, mul_zero]