Lemma 32, p. 31 — for small ε there is a number k of copies matching 1 − (1 − p)^σ and p up to a factor 1 + λ
ProvedAPrioriTSP.Sampling.lemma_32a-priori-tspapproximation-algorithmsp2o-batch-pfp2ap2o-gran-per-chapterp2o-plan-paperp2o-v1random-samplingstochastic-combinatorial-optimization
Let , and . Then there is such that for every there is with
- ,
- ,
- ,
- if , and if .
In the proof of Lemma 9, each customer is replaced by copies of activation probability ; the lemma controls the probability that some copy is active or sampled.
Formalization Note is the real power; and are natural-number powers. The variable is named lam (a Lean keyword otherwise).
Differences from the source:
- encoding: k ∈ ℕ → k : ℕ (0 included); reason: the paper's ℕ contains 0 (Lemma 18's base case n = 0); item (i) forces k ≥ 1 anyway, since p > 0
Preamble
import Mathlib import Definitions.Def_APrioriTSP_Sampling_Setting
Formal statement
namespace APrioriTSP.Sampling
/-- Lemma 32 (p. 31): choosing the number `k` of copies of a customer. -/
theorem lemma_32 (σ lam p : ℝ) (hσ0 : 0 < σ) (hσ1 : σ < 1) (hlam : 0 < lam)
(hp0 : 0 < p) (hp1 : p ≤ 1) :
∃ εp : ℝ, 0 < εp ∧ εp < 1 ∧ ∀ ε : ℝ, 0 < ε → ε ≤ εp → ∃ k : ℕ,
(1 - (1 - ε) ^ k ≤ p ∧ p ≤ ε * k) ∧
(1 - p) ^ σ ≤ (1 - σ * ε) ^ k ∧
1 - (1 - p) ^ σ ≤ (1 + lam) * (1 - (1 - σ * ε) ^ k) ∧
(p < 1 → (1 - ε) ^ k ≤ (1 + lam) * (1 - p)) ∧
(p = 1 → (1 - ε) ^ k ≤ lam) := by sorry
end APrioriTSP.Sampling
Source
Blauth, Neuwohner, Puhlmann & Vygen, Improved guarantees for the a priori TSP, arXiv:2309.10663v1, p. 31, Lemma 32
Human review
Confirmed by the mission captain (proposal self-audit).
Confirmed by the moderator at approval.