Proposition 12, p. 10 — buckets of a sequence satisfying the triangle inequality satisfy B_{i+j} ≤ B_i + B_j
ProvedAPrioriTSP.Sampling.proposition_12a-priori-tspapproximation-algorithmslinear-programmingp2o-batch-pfp2ap2o-gran-per-chapterp2o-plan-paperp2o-strengthenedp2o-v1random-samplingstochastic-combinatorial-optimization
Let be odd and let be real numbers with for all (constraint (7)). Define the buckets
Then for all ,
The buckets aggregate consecutive hop sums around ; the proposition says that this aggregation keeps the triangle inequality, which becomes constraint (14) of (Sampling-LP).
Differences from the source:
- generalization: the buckets of a feasible solution C of (Sampling-OP) → the buckets of any real sequence C satisfying (7); reason: the proof uses only (7); feasible solutions satisfy (7)
- encoding: an odd integer b ≥ b_0 for the constant b_0 > 0 of §2 (p. 7) → every odd natural number b; reason: b_0 is an arbitrary positive constant, so every odd b ≥ 1 qualifies with b_0 := b
Preamble
import Mathlib import Definitions.Def_APrioriTSP_Sampling_Setting import Definitions.Def_APrioriTSP_Sampling_LP
Formal statement
namespace APrioriTSP.Sampling
/-- Proposition 12 (p. 10): buckets of odd size `b` of a sequence satisfying the triangle
inequality (7) satisfy `B_{i+j} ≤ B_i + B_j` for all `i, j ≥ 1`. -/
theorem proposition_12 (b : ℕ) (hb : Odd b) (C : ℕ → ℝ)
(hC : ∀ i j, 1 ≤ i → 1 ≤ j → C (i + j) ≤ C i + C j) :
∀ i j, 1 ≤ i → 1 ≤ j → bucket b C (i + j) ≤ bucket b C i + bucket b C j := by sorry
end APrioriTSP.Sampling
Source
Blauth, Neuwohner, Puhlmann & Vygen, Improved guarantees for the a priori TSP, arXiv:2309.10663v1, p. 10, Proposition 12 and Equation (9)
Human review
Confirmed by the mission captain (proposal self-audit).
Confirmed by the moderator at approval.