§3.2 — and the stable buckets (corrected: half-open jumps, Figure 1 indexing)
ProvedFreeOrderEPTAS.bucket_factsapproximation-schemep2o-correctedp2o-gran-per-chapterp2o-plan-paperp2o-strengthenedp2o-v1prophet-inequalitystochastic-optimization
Let be a permutation with and a positive integer. For the corrected buckets:
- ;
- every stable bucket has , strictly if ;
- every jump bucket holds exactly one variable;
- every variable lies in one of the buckets;
- on a nonempty bucket, ;
- , and at the index above the top bucket .
These are the facts about the partition that Claims 3.4 and 3.5 use.
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
- generalization: an optimal permutation → every permutation ; reason: no step uses optimality; is a permutation
- reading: , undefined → at the index above the top bucket; reason: the value (15) needs at the top bucket; for optimal
- 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
Preamble
import Mathlib import Definitions.Def_FreeOrderEPTAS_bucket
Formal statement
namespace FreeOrderEPTAS
/-- §3.2, pp.17–18 (arXiv:2007.13121v3), for the corrected buckets of any permutation `σ` with
`1/ϵ ∈ ℕ`, where `V*_s = R I σ s` (0-based) and `K = numJumps`:
1. `K ≤ 1/ϵ`;
2. every stable (even) bucket has `BaseVal(B_{i+1}) - BaseVal(B_i) ≤ ϵ V*_0`, strictly when `V*_0 > 0`;
3. every jump (odd) bucket consists of exactly one variable;
4. the buckets are `0, …, 2K`;
5. `BaseVal(B_i) = V*_{max{t : X_{σ(t)} ∈ B_i}+1}` on a nonempty bucket;
6. `BaseVal(B_1) = 0`, and at the index `2K + 1` above the top bucket `BaseVal = V*_0`. -/
theorem bucket_facts {n : ℕ} (I : Instance n) (σ : Equiv.Perm (Fin n)) (ϵ : ℝ) (q : ℕ) (hq : 0 < q)
(hϵ : ϵ = 1 / (q : ℝ)) :
(numJumps I σ ϵ : ℝ) ≤ 1 / ϵ ∧
(∀ i, i < 2 * numJumps I σ ϵ + 1 → Even i →
BaseVal I σ ϵ (i + 1) - BaseVal I σ ϵ i ≤ ϵ * R I σ 0 ∧
(0 < R I σ 0 → BaseVal I σ ϵ (i + 1) - BaseVal I σ ϵ i < ϵ * R I σ 0)) ∧
(∀ i, i < 2 * numJumps I σ ϵ + 1 → Odd i → ∃! s, s < n ∧ bucket I σ ϵ s = i) ∧
(∀ s, s < n → bucket I σ ϵ s < 2 * numJumps I σ ϵ + 1) ∧
(∀ s, s < n → (∀ s', s' < n → bucket I σ ϵ s' = bucket I σ ϵ s → s' ≤ s) →
BaseVal I σ ϵ (bucket I σ ϵ s) = R I σ (s + 1)) ∧
BaseVal I σ ϵ 0 = 0 ∧
BaseVal I σ ϵ (2 * numJumps I σ ϵ + 1) = R I σ 0 := by sorry
end FreeOrderEPTAS
Source
Segev & Singla, Efficient Approximation Schemes for Stochastic Probing and Selection-Stopping Problems, arXiv:2007.13121v3, §3.2, pp.17–18, Figure 1
Human review
Confirmed by the mission captain (proposal self-audit).
Confirmed by the moderator at approval.