Lemma 2.3 — (IV) violated by at most (corrected: capped small-load guess)
ProvedFreeOrderEPTAS.lemma_2_3approximation-schemep2o-correctedp2o-gran-per-chapterp2o-plan-paperp2o-strengthenedp2o-v1prophet-inequalitystochastic-optimization
Let , , with (9), let satisfy (IV), with its induced guesses, feasible for (LP), and a rounding with (P1)–(P3). Then
With the capped guess the proof uses in (5).
Differences from the source:
- correction: , p.10 → ; reason: the printed guess has order values ( jobs of load in one class, all on machine ), a PTAS count against the stated ; every step of the proof survives the cap
- generalization: the of p.12, feasible → any with (9) when , and satisfying (IV) only; reason: the proof uses (9) and (IV) of only; when there is no active pair, or no job and then (IV) forces no active pair
Preamble
import Mathlib import Definitions.Def_FreeOrderEPTAS_mkLP import Definitions.Def_FreeOrderEPTAS_IsInducedGuess import Definitions.Def_FreeOrderEPTAS_IsDependentRounding
Formal statement
namespace FreeOrderEPTAS
/-- Lemma 2.3, p.13 (arXiv:2007.13121v3): `P(X violates (IV) by at most 2ϵ) ≥ 1/2`, for `x^(IP)`
feasible, the guesses it induces, `y` feasible for (LP), `ξ = ϵ/2`, and `δ` with (9). -/
theorem lemma_2_3 {m D n : ℕ} (I : SCInstance m D n) (ϵ δ : ℝ) (hϵ0 : 0 < ϵ) (hϵ1 : ϵ < 1)
(hδ0 : 0 < δ) (hδ1 : δ < 1)
(h9 : 0 < m * D * numTypes I ϵ δ → δ ≤ ϵ ^ 3 / (16 * (numTypes I ϵ δ : ℝ) *
Real.log (2 * (m : ℝ) * (D : ℝ) * (numTypes I ϵ δ : ℝ))))
(x : Assignment m n) (hload : LoadAtLeast I x 1)
(Nlo Nhi : Fin m → Fin (numTypes I ϵ δ) → ℕ)
(Slo : Fin m → Fin D → Fin (numTypes I ϵ δ) → ℝ)
(hg : IsInducedGuess I ϵ δ (ϵ / 2) x Nlo Nhi Slo)
(y : (mkLP I ϵ δ (ϵ / 2) Nlo Nhi Slo).Vars) (hy : (mkLP I ϵ δ (ϵ / 2) Nlo Nhi Slo).Feasible y)
(rnd : Rounding) (hrnd : IsDependentRounding rnd) :
(1 / 2 : ℝ) ≤ pr (rnd (mkLP I ϵ δ (ϵ / 2) Nlo Nhi Slo) y)
{Y | LoadAtLeast I Y (1 - 2 * ϵ)} := by sorry
end FreeOrderEPTAS
Source
Segev & Singla, Efficient Approximation Schemes for Stochastic Probing and Selection-Stopping Problems, arXiv:2007.13121v3, Lemma 2.3, p.13; (5), p.14
Human review
Confirmed by the mission captain (proposal self-audit).
Confirmed by the moderator at approval.