Lemma 3.2 — (IPProphets) is feasible (corrected: guess grid, buckets)
ProvedFreeOrderEPTAS.lemma_3_2approximation-schemep2o-correctedp2o-gran-per-chapterp2o-plan-paperp2o-v1prophet-inequalitystochastic-optimization
Let be optimal and a positive integer. For all guesses satisfying (14) and (15), (IPProphets) admits a feasible solution. Moreover, if and , then guesses satisfying (14) and (15) exist on the grid .
This is why the enumeration of §3.3 reaches a feasible Santa Claus instance.
Differences from the source:
- correction: grid , p.18 → grid ; reason: can exceed : , , the identity, , where (14) needs a guess in , above the printed top
- 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
- 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 - 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" - 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
Preamble
import Mathlib import Definitions.Def_FreeOrderEPTAS_IsGuess import Definitions.Def_FreeOrderEPTAS_IPProphets import Definitions.Def_FreeOrderEPTAS_OPT import Definitions.Def_FreeOrderEPTAS_freeOrder
Formal statement
namespace FreeOrderEPTAS
/-- Lemma 3.2, p.19 (arXiv:2007.13121v3), for `σ*` optimal and `1/ϵ ∈ ℕ`: for guesses satisfying (14)
and (15), (IPProphets) admits a feasible solution. Also, when `E ∈ [(1 - ϵ) OPT, OPT]` with
`ϵ < 1`, such guesses exist on the corrected grid `{k ϵ²E : 0 ≤ k ≤ ⌈1/(ϵ²(1 - ϵ))⌉}`. -/
theorem lemma_3_2 {n : ℕ} (I : Instance n) (σs : Equiv.Perm (Fin n)) (hopt : V I σs = OPT I)
(ϵ E : ℝ) (q : ℕ) (hq : 0 < q) (hϵ : ϵ = 1 / (q : ℝ)) :
(∀ b Δ : Fin (2 * numJumps I σs ϵ + 1) → ℝ, IsGuess I σs ϵ E b Δ →
IPProphetsFeasible I b Δ) ∧
(ϵ < 1 → (1 - ϵ) * OPT I ≤ E → E ≤ OPT I →
∃ b Δ : Fin (2 * numJumps I σs ϵ + 1) → ℝ, IsGuess I σs ϵ E b Δ ∧
∀ i, b i ∈ guessGrid ϵ E ⌈1 / (ϵ ^ 2 * (1 - ϵ))⌉₊ ∧
Δ i ∈ guessGrid ϵ E ⌈1 / (ϵ ^ 2 * (1 - ϵ))⌉₊) := by sorry
end FreeOrderEPTAS
Source
Segev & Singla, Efficient Approximation Schemes for Stochastic Probing and Selection-Stopping Problems, arXiv:2007.13121v3, Lemma 3.2, p.19; (14), (15), p.18
Human review
Confirmed by the mission captain (proposal self-audit).
Confirmed by the moderator at approval.