Lemma 14, p. 12 — the error term beyond bucket N is at most δ1·Σ_{k=0}^N e^{−(k−1)σβ}·B_k + δ2·B_1
ProvedAPrioriTSP.Sampling.lemma_14a-priori-tspapproximation-algorithmslinear-programmingp2o-batch-pfp2ap2o-gran-per-chapterp2o-plan-paperp2o-strengthenedp2o-v1random-samplingstochastic-combinatorial-optimization
Let , , and , and let be nonnegative with for all . With
we have
The lemma bounds the contribution of buckets beyond to the bucket form (10) of the sampling constraint by terms in only, which is what makes (Sampling-LP) finite.
Formalization Note The first series is a tsum over of terms that vanish for ; the double series is a tsum over of terms that vanish when . Under the hypotheses for , so both families are summable. Exponents are real: gives .
Differences from the source:
- reading: δ1 · Σ_{k=0}^N e^{−(k−1)·σβ} · B_i (the summand's index i is unbound) → δ1 · Σ_{k=0}^N e^{−(k−1)σβ} · B_k; reason: the only well-formed reading; it is the sum (11) and (13) use, and the proof's last line (p. 14) has the same sum with index and summand i
- generalization: the buckets B of a feasible solution of (Sampling-OP) (B ≥ 0 and Proposition 12) → any sequence B ≥ 0 with B_{i+j} ≤ B_i + B_j for i, j ≥ 1; reason: the proof uses only these two properties, which the buckets of a feasible solution have
- generalization: α ≥ 1, the approximation guarantee of the TSP algorithm of step (ii) (p. 4) → every real α ≥ 0; reason: (2) is a formula in α and the argument uses only α ≥ 0; at every α ≥ 1 the Lean statement is the paper's
- generalization: σ = 0.663, fixed at the start of §2 (p. 7) → every σ > 0; reason: the proof uses only σβ > 0; σ = 0.663 is an instance
- encoding: N an integer (the buckets B_0, …, B_N) → N ∈ ℕ; reason: N indexes the buckets kept, so N ≥ 0
- encoding: the series over k ≥ N + 1 and over i, j ∈ ℤ_{≥0} with max{i, j} > N →
tsums over ℕ and ℕ × ℕ of the terms multiplied by the indicator of the index range; reason: same sums; the families are nonnegative and summable since B_k ≤ k·B_1
Preamble
import Mathlib import Definitions.Def_APrioriTSP_Sampling_Setting import Definitions.Def_APrioriTSP_Sampling_LP
Formal statement
namespace APrioriTSP.Sampling
/-- Lemma 14 (p. 12): the error term beyond bucket `N` is bounded by
`δ₁ Σ_{k=0}^N e^{−(k−1)σβ} B_k + δ₂ B_1`. -/
theorem lemma_14 (α σ β : ℝ) (hα : 0 ≤ α) (hσ : 0 < σ) (hβ : 0 < β) (N : ℕ)
(B : ℕ → ℝ) (hB0 : ∀ i, 0 ≤ B i)
(hB : ∀ i j, 1 ≤ i → 1 ≤ j → B (i + j) ≤ B i + B j) :
α * ∑' k : ℕ, (if N < k then Real.exp (-(((k : ℝ) - 1) * σ * β)) * B k else 0) +
2 * β * ∑' q : ℕ × ℕ, (if N < max q.1 q.2 then
Real.exp (-(((q.1 : ℝ) + q.2 - 1) * σ * β)) * min (B q.1) (B q.2) else 0) ≤
delta1 β σ N * ∑ k ∈ Finset.range (N + 1), Real.exp (-(((k : ℝ) - 1) * σ * β)) * B k +
delta2 α β σ N * B 1 := by sorry
end APrioriTSP.Sampling
Source
Blauth, Neuwohner, Puhlmann & Vygen, Improved guarantees for the a priori TSP, arXiv:2309.10663v1, p. 12, Lemma 14 (proof p. 14)
Human review
Confirmed by the mission captain (proposal self-audit).
Confirmed by the moderator at approval.