p.17 — and the estimate (corrected: grid relative to )
ProvedFreeOrderEPTAS.estimateapproximation-schemep2o-correctedp2o-gran-per-chapterp2o-plan-paperp2o-strengthenedp2o-v1prophet-inequalitystochastic-optimization
For every permutation ,
Moreover, if , then some with lies in .
The first part is the classical prophet inequality, and the published item MatroidProphetKW.RankOne.half_mean_threshold gives it for a threshold rule.
Differences from the source:
- correction: "all powers of within the interval " → ; reason: one variable with value , : then , the required is , not a power of
- encoding: →
⨆ i, x i, which is at ; reason: the supremum of a finite family; the empty case has value on both sides - generalization: an integer → any ; reason: the proof uses no integrality; the integer case is covered
Preamble
import Mathlib import Definitions.Def_FreeOrderEPTAS_OPT open MeasureTheory
Formal statement
namespace FreeOrderEPTAS
/-- p.17 (arXiv:2007.13121v3): the prophet inequality `V(σ) ≥ ½ E[max_j X_j] ≥ ½ OPT` for every
`σ`, and some `E = V(σ₀)(1 + ϵ)^k` with `0 ≤ k ≤ ⌈log 2 / log(1 + ϵ)⌉` lies in
`[(1 - ϵ) OPT, OPT]`. -/
theorem estimate {n : ℕ} (I : Instance n) :
(∀ σ, (∫ x : Fin n → ℝ, ⨆ i, x i ∂(Measure.pi I.μ)) / 2 ≤ V I σ) ∧
OPT I ≤ ∫ x : Fin n → ℝ, ⨆ i, x i ∂(Measure.pi I.μ) ∧
(∀ σ, OPT I ≤ 2 * V I σ) ∧
∀ (σ₀ : Equiv.Perm (Fin n)) (ϵ : ℝ), 0 < ϵ → ϵ ≤ 1 →
∃ k : ℕ, k ≤ ⌈Real.log 2 / Real.log (1 + ϵ)⌉₊ ∧
(1 - ϵ) * OPT I ≤ V I σ₀ * (1 + ϵ) ^ k ∧ V I σ₀ * (1 + ϵ) ^ k ≤ OPT I := by sorry
end FreeOrderEPTAS
Source
Segev & Singla, Efficient Approximation Schemes for Stochastic Probing and Selection-Stopping Problems, arXiv:2007.13121v3, §3.2, p.17
Human review
Confirmed by the mission captain (proposal self-audit).
Confirmed by the moderator at approval.