Claim 2.4 — concentration of the small jobs
ProvedFreeOrderEPTAS.claim_2_4approximation-schemep2o-gran-per-chapterp2o-plan-paperp2o-strengthenedp2o-v1prophet-inequalitystochastic-optimization
Let , , with (9), feasible for (LP), and a rounding with (P1)–(P3). For with , if is an integer multiple of then
This is where is used: small jobs have load at most , so (P3) applies to .
Differences from the source:
- generalization: and the of p.12 → any integer multiple of , and any with (9); reason: the proof uses exactly these two facts, and covers the capped guess
Preamble
import Mathlib import Definitions.Def_FreeOrderEPTAS_mkLP import Definitions.Def_FreeOrderEPTAS_IsDependentRounding
Formal statement
namespace FreeOrderEPTAS
/-- Claim 2.4, p.14 (arXiv:2007.13121v3): `P((A)_idt ≥ (1 - ϵ) S↓_idt) ≥ 1 - 1/(2mDT)`, for a small
triple, `y` feasible for (LP), `ξ = ϵ/2`, `δ` with (9), and `S↓_idt` a multiple of `ϵ/T`. -/
theorem claim_2_4 {m D n : ℕ} (I : SCInstance m D n) (ϵ δ : ℝ) (hϵ0 : 0 < ϵ) (hϵ1 : ϵ < 1)
(hδ0 : 0 < δ) (hδ1 : δ < 1)
(h9 : δ ≤ ϵ ^ 3 / (16 * (numTypes I ϵ δ : ℝ) *
Real.log (2 * (m : ℝ) * (D : ℝ) * (numTypes I ϵ δ : ℝ))))
(Nlo Nhi : Fin m → Fin (numTypes I ϵ δ) → ℕ)
(Slo : Fin m → Fin D → Fin (numTypes I ϵ δ) → ℝ)
(y : (mkLP I ϵ δ (ϵ / 2) Nlo Nhi Slo).Vars) (hy : (mkLP I ϵ δ (ϵ / 2) Nlo Nhi Slo).Feasible y)
(rnd : Rounding) (hrnd : IsDependentRounding rnd)
(i : Fin m) (d : Fin D) (t : Fin (numTypes I ϵ δ)) (hd : d ∈ I.A i)
(hsmall : typeOf I ϵ δ t i d = 0)
(hS : ∃ k : ℕ, Slo i d t = (k : ℝ) * (ϵ / (numTypes I ϵ δ : ℝ))) :
1 - 1 / (2 * (m : ℝ) * (D : ℝ) * (numTypes I ϵ δ : ℝ)) ≤
pr (rnd (mkLP I ϵ δ (ϵ / 2) Nlo Nhi Slo) y)
{Y | (1 - ϵ) * Slo i d t ≤ ∑ j with rho I ϵ δ j = t, I.ℓ i j d * bit (Y i j)} := by sorry
end FreeOrderEPTAS
Source
Segev & Singla, Efficient Approximation Schemes for Stochastic Probing and Selection-Stopping Problems, arXiv:2007.13121v3, Claim 2.4, p.14; proof, pp.15–16
Human review
Confirmed by the mission captain (proposal self-audit).
Confirmed by the moderator at approval.