Proof of Lemma 5, p. 7 — after round trip j, all but α·#{latency > 2^jδ} points are visited, each with latency ≤ β2^{j+2}δ
ProvedMinLatency.Approx.lemma_5_round_tripLet be a metric on a finite set with , let , let be the distance from to its nearest neighbour, and let be an -TSP-approximator for . Write for the th round trip and for the walk after round trip . Let be any walk from visiting every point, and write for the latency of in . Then for all :
- (coverage) the number of points visited by satisfies
- (latency) every point visited by has latency in at most
This is the step of the proof of Lemma 5 that charges the points of the algorithm's walk against the optimal one: when only few points of the optimal walk have latency above , the th round trip has already visited all but times as many points, and those points were reached within .
Formalization Note The page assumes "for simplicity of presentation"; here is explicit, and round trip uses the budget , the page's .
Differences from the source:
- encoding: the nearest-neighbour distance is normalised to 1; budgets L = 2, 4, 8, …; bound β2^{j+2} → δ = nnDist d p explicit; budgets 2^{j+1}δ; bound β·2^{j+2}·δ; reason: scaling all distances by 1/δ gives the page's normalised statement
- reading: the blocks B_i of α vertices of our tour and the set S_j of optimal vertices of latency between 2^{j−1} and 2^j, with 'the n − ith vertex visited by the optimal tour' in S_j and i = (1 − ε)n → coverage clause: the points visited by round trips 0, …, j number at least n − α·#{v : t_σ(v) > 2^jδ}; reason: the page's indices do not parse literally; the clause is the sentence's content: when at most m optimal points have latency above 2^jδ, all but αm points are visited by round trip j
- reading: visited by our jth round trip → visited by one of the round trips 0, …, j; reason: the latency bound β(2∗2^j + 2∗2^{j−1} + ⋯) sums the round trips 0, …, j
- generalization: the minimum latency tour → any walk σ from p that visits every point; reason: the statement holds for every covering walk, in particular for an optimal one
- generalization: α, β are the ratios of an approximator (implicitly α, β ≥ 1) → α, β arbitrary reals, no sign hypothesis; reason: specializes to α, β ≥ 1; for α ≤ 0 or β < 0 on two or more points no approximator exists, and one point has latency 0
- reading: an approximator given ε and L, visiting at least (1 − αε)n vertices if a tour of length L visits (1 − ε)n vertices (Definition and Comment, p. 6) → IsTSPApprox: A is called with L only and, for every k, if some rooted tour of closed length ≤ L misses ≤ k points then A L is a rooted tour of closed length ≤ βL missing ≤ αk points; reason: the Comment allows calling the approximator with L only, and Lemma 5 does so; εn = k is the number of missed points; 'a tour of length L' is read as closed length at most L
- reading: bounds L of the Definition (p. 6) → 0 < L; reason: L is a tour-length budget; at L = 0 the page's penalty P = 2L/(εn) is 0 and its argument ('else the penalty is more than 6L') is void; Lemma 5 calls the approximator only with L = 2^{j+1}δ > 0
- reading: the distances satisfy the triangle inequality / an n-point metric space (§3.2, p. 6) → IsMetric d: symmetric, zero diagonal, positive between distinct points, triangle inequality; reason: positivity is §3.2's standing assumption (metric spaces; the proof of Lemma 5 normalises the nearest-neighbour distance to 1); without it the algorithm fails: p and z_1, …, z_m at mutual distance 0 and f at distance 1 from all of them give δ = 0, and even with δ repaired to 1 a factor-2 oracle may return (p, f, z_1, …, z_m) at L = 2, with latency 1 + 2m against 1 for (p, z_1, …, z_m, f)
- reading: a tour starting at p (Definition and prize-collecting problem, p. 6) → IsRootedTour p T: a duplicate-free list with head p, closed by the return leg to p (tourLen); reason: a TSP tour visits each of its points once and returns to its start; the GW algorithm returns such a tour, and under the triangle inequality any closed walk from p shortcuts to one that is no longer and visits the same points, so no instance of the page changes
import Mathlib import Definitions.Def_MinLatency_Approx_Setting
namespace MinLatency.Approx
theorem lemma_5_round_trip {V : Type} [Fintype V] [DecidableEq V]
(d : V → V → ℝ) (p : V) (hd : IsMetric d) (α β : ℝ) (A : ℝ → List V)
(hA : IsTSPApprox d p α β A) (σ : List V) (hσ : IsCoveringWalk p σ)
(j J : ℕ) (hjJ : j ≤ J) :
(Fintype.card V : ℝ) - α * ((Finset.univ.filter
(fun v => (2 : ℝ) ^ j * nnDist d p < firstVisit d σ v)).card : ℝ)
≤ ((Finset.univ.filter (fun v => ∃ i ≤ j, v ∈ A (budget d p i))).card : ℝ) ∧
∀ v, (∃ i ≤ j, v ∈ A (budget d p i)) →
firstVisit d (doublingWalk d p A J) v ≤ β * (2 : ℝ) ^ (j + 2) * nnDist d p := by sorry
end MinLatency.Approx
Confirmed by the mission captain (proposal self-audit).
Confirmed by the moderator at approval.