§3.5 — (corrected: buckets)
ProvedFreeOrderEPTAS.value_guaranteeapproximation-schemep2o-correctedp2o-gran-per-chapterp2o-plan-paperp2o-v1prophet-inequalitystochastic-optimization
Under the situation of §3.5, the permutation built from the assignment satisfies
It combines Claims 3.4 and 3.5 with , or with Claim 3.5 alone if no time is ahead of schedule.
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: the permutation orders the assigned variables only → unassigned variables come after all assigned ones; reason: §3.5 is silent; a total permutation is needed
- 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
/-- §3.5, pp.20, 22 (arXiv:2007.13121v3): the permutation built from the assignment of Corollary 3.3
has `V(σ) ≥ (1 - 7ϵ) OPT`. -/
theorem value_guarantee {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) :
(1 - 7 * ϵ) * OPT I ≤ V I (orderOf x) := by sorry
end FreeOrderEPTAS
Source
Segev & Singla, Efficient Approximation Schemes for Stochastic Probing and Selection-Stopping Problems, arXiv:2007.13121v3, §3.5, pp.20, 22; (16), p.21
Human review
Confirmed by the mission captain (proposal self-audit).
Confirmed by the moderator at approval.