§2.5, inequality (9): the explicit is calibrated
ProvedFreeOrderEPTAS.delta_calibrationapproximation-schemep2o-gran-per-chapterp2o-plan-paperp2o-v1prophet-inequalitystochastic-optimization
Let and let with . For any Santa Claus instance, with the number of classes induced by and ,
This is the calibration that makes the union bound of Lemma 2.3 close: the number of classes grows only polylogarithmically in .
Differences from the source:
- reading: , assuming is an integer, for a constant not specified → explicit with ; reason: the source only requires (9) and an integer , depending on ; the explicit value has both
- encoding: (9), used for a small triple , with → hypotheses and ; reason: at the right side divides by , a junk value , and no triple exists; "small constants ", p.9
Preamble
import Mathlib import Definitions.Def_FreeOrderEPTAS_typeList import Definitions.Def_FreeOrderEPTAS_delta
Formal statement
namespace FreeOrderEPTAS
/-- §2.5, p.12 and the end of the proof of Claim 2.4, pp.15–16 (arXiv:2007.13121v3): the explicit
`δ = 2^{-r}` satisfies inequality (9), `δ ≤ ϵ³ / (16 T ln(2mDT))`, for the number `T` of classes it
induces. -/
theorem delta_calibration {m D n : ℕ} (I : SCInstance m D n) (ϵ : ℝ) (hϵ0 : 0 < ϵ) (hϵ1 : ϵ < 1)
(hpos : 0 < m * D * numTypes I ϵ (delta ϵ m D)) :
delta ϵ m D ≤ ϵ ^ 3 / (16 * (numTypes I ϵ (delta ϵ m D) : ℝ) *
Real.log (2 * (m : ℝ) * (D : ℝ) * (numTypes I ϵ (delta ϵ m D) : ℝ))) := by sorry
end FreeOrderEPTAS
Source
Segev & Singla, Efficient Approximation Schemes for Stochastic Probing and Selection-Stopping Problems, arXiv:2007.13121v3, §2.5, p.12; inequality (9), pp.15–16
Human review
Confirmed by the mission captain (proposal self-audit).
Confirmed by the moderator at approval.