Claim 3.4 — the value at (corrected: buckets)
ProvedFreeOrderEPTAS.claim_3_4approximation-schemep2o-correctedp2o-gran-per-chapterp2o-plan-paperp2o-v1prophet-inequalitystochastic-optimization
Under the situation of §3.5, let be the minimal time when is ahead of schedule, with on the machine of bucket . Then
The stable case uses , which needs the corrected buckets.
Differences from the source:
- correction: jump iff the closed interval contains a multiple of ; , p.17 → jump variable at iff contains a multiple; buckets as in Figure 1; reason: , values , the identity: closed intervals give ; values : the text’s stable bucket has step , against Figure 1 and the proof of Claim 3.4
- reading: "This index is well-defined, since we are always ahead of schedule at time " → exists and is assigned, as hypotheses; reason: the printed reason assumes that sits on machine 1, which may hold nothing; the other case is the second part of
claim_3_5 - encoding: times and buckets and → 0-based
Fin n,Fin (2K+1); even index stable, odd index jump; reason: a shift of indices; same objects - reading: , needed in (15) for the top bucket, undefined → (
BaseValat the index ); reason: the value (15) needs at the top bucket; it is for optimal - encoding: the guesses are read from the enumerated grid → non-negativity is a clause of
IsGuess; reason: the grid is non-negative; p.20 uses "the non-negativity of BaseGuess"
Preamble
import Mathlib import Definitions.Def_FreeOrderEPTAS_Schedule import Definitions.Def_FreeOrderEPTAS_orderOf
Formal statement
namespace FreeOrderEPTAS
/-- Claim 3.4, p.21 (arXiv:2007.13121v3):
`R_{t_min} ≥ BaseVal(B) + (1 - ϵ) DeltaGuess(B) - 2ϵ OPT`, for the bucket `B` of `X_{σ(t_min)}`. -/
theorem claim_3_4 {n : ℕ} (I : Instance n) (σs : Equiv.Perm (Fin n)) (ϵ E : ℝ)
(b Δ : Fin (2 * numJumps I σs ϵ + 1) → ℝ) (x : Assignment (2 * numJumps I σs ϵ + 1) n)
(h : Schedule I σs ϵ E b Δ x) (t : Fin n) (i : Fin (2 * numJumps I σs ϵ + 1))
(ht : IsFirstAhead I (orderOf x) b x t i) :
BaseVal I σs ϵ i.val + (1 - ϵ) * Δ i - 2 * ϵ * OPT I ≤ R I (orderOf x) t.val := by sorry
end FreeOrderEPTAS
Source
Segev & Singla, Efficient Approximation Schemes for Stochastic Probing and Selection-Stopping Problems, arXiv:2007.13121v3, Claim 3.4, p.21
Human review
Confirmed by the mission captain (proposal self-audit).
Confirmed by the moderator at approval.