Claim 2.5 — large jobs (corrected: capped small-load guess)
ProvedFreeOrderEPTAS.claim_2_5approximation-schemep2o-correctedp2o-gran-per-chapterp2o-plan-paperp2o-strengthenedp2o-v1prophet-inequalitystochastic-optimization
Let , the guesses induced by , meeting (S1)–(S3), and a rounding with (P2). For with , every in the support satisfies
It uses and the geometric segments of the type.
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: , feasible for (LP), for feasible and → any meeting (S1)–(S3), any binary , any ; reason: the proof uses (P2) and only; the source’s case is covered
- encoding: "with probability 1" → for every point of the support of the law; reason: the laws are on a finite set
Preamble
import Mathlib import Definitions.Def_FreeOrderEPTAS_mkLP import Definitions.Def_FreeOrderEPTAS_IsInducedGuess import Definitions.Def_FreeOrderEPTAS_IsDependentRounding
Formal statement
namespace FreeOrderEPTAS
/-- Claim 2.5, p.14 (arXiv:2007.13121v3): with probability 1,
`(B)_idt ≥ (1 - ϵ) min{∑_{j ∈ J_t} ℓ_ijd x^(IP)_ij, 1}` on a class with `T^(t)_id ≥ 1`. -/
theorem claim_2_5 {m D n : ℕ} (I : SCInstance m D n) (ϵ δ ξ : ℝ) (hϵ0 : 0 < ϵ) (hϵ1 : ϵ < 1)
(hδ0 : 0 < δ) (hδ1 : δ < 1) (x : Assignment m n)
(Nlo Nhi : Fin m → Fin (numTypes I ϵ δ) → ℕ)
(Slo : Fin m → Fin D → Fin (numTypes I ϵ δ) → ℝ)
(hg : IsInducedGuess I ϵ δ ξ x Nlo Nhi Slo)
(y : (mkLP I ϵ δ ξ Nlo Nhi Slo).Vars) (hy : (mkLP I ϵ δ ξ Nlo Nhi Slo).MeetsS123 y)
(rnd : Rounding) (hrnd : IsDependentRounding rnd)
(Y : Assignment m n) (hY : Y ∈ (rnd (mkLP I ϵ δ ξ Nlo Nhi Slo) y).support)
(i : Fin m) (d : Fin D) (t : Fin (numTypes I ϵ δ)) (hd : d ∈ I.A i)
(hlarge : 1 ≤ typeOf I ϵ δ t i d) :
(1 - ϵ) * min (Sip I ϵ δ x i d t) 1 ≤
∑ 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.5, p.14; proof, p.16
Human review
Confirmed by the mission captain (proposal self-audit).
Confirmed by the moderator at approval.