Claim 3.5 — the value before (corrected: buckets)
ProvedFreeOrderEPTAS.claim_3_5approximation-schemep2o-correctedp2o-gran-per-chapterp2o-plan-paperp2o-v1prophet-inequalitystochastic-optimization
Under the situation of §3.5, with and as in Claim 3.4,
If no time is ahead of schedule, the same bound holds with and the sum over all buckets.
The constant comes from in (19).
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: always exists → a second part for the case that no time is ahead, with ; reason: machine 1 may be empty
- 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.5, p.21 (arXiv:2007.13121v3):
`∑_{t < t_min} (R_t - R_{t+1}) ≥ (1 - ϵ) ∑_{i > B} (BaseVal(B_{i+1}) - BaseVal(B_i)) - 3ϵ OPT`, for
the bucket `B` of `X_{σ(t_min)}`. Second part: if no time is ahead of schedule, the same bound with
`t_min = n + 1` and the sum over all buckets. -/
theorem claim_3_5 {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)), IsFirstAhead I (orderOf x) b x t i₀ →
(1 - ϵ) * ∑ i with i₀ < i, (BaseVal I σs ϵ (i.val + 1) - BaseVal I σs ϵ i.val) -
3 * ϵ * OPT I ≤
∑ t' ∈ Finset.range t.val, (R I (orderOf x) t' - R I (orderOf x) (t' + 1))) ∧
((∀ (t : Fin n) (i : Fin (2 * numJumps I σs ϵ + 1)), x i (orderOf x t) = true →
R I (orderOf x) (t.val + 1) < b i) →
(1 - ϵ) * ∑ i : Fin (2 * numJumps I σs ϵ + 1),
(BaseVal I σs ϵ (i.val + 1) - BaseVal I σs ϵ i.val) - 3 * ϵ * OPT I ≤
∑ t' ∈ Finset.range n, (R I (orderOf x) t' - R I (orderOf x) (t' + 1))) := by sorry
end FreeOrderEPTAS
Source
Segev & Singla, Efficient Approximation Schemes for Stochastic Probing and Selection-Stopping Problems, arXiv:2007.13121v3, Claim 3.5, p.21; (18), (19), p.22
Human review
Confirmed by the mission captain (proposal self-audit).
Confirmed by the moderator at approval.