The ratio of is exactly
ProvedTSPHeuristics.NNLower.gbar_ratio_exactnearest-neighborp2o-batch-p100ap2o-gran-per-chapterp2o-plan-paperp2o-v1traveling-salesman
Let , , and let be the tour of that visits the nodes in the order of the path and returns to the start node. Then
Together with property b), this is the ratio NEARNEIBER/OPTIMAL of the instance (p. 569, where ).
Formalization Note is the solution of , .
Preamble
import Mathlib import Definitions.Def_TSPHeuristics_NNLower_TSPModel import Definitions.Def_TSPHeuristics_NNLower_LowerBoundFamily
Formal statement
namespace TSPHeuristics.NNLower
/-- p. 569: for `i ≥ 1`, the tour of `Ḡ_i` visiting the nodes in the order of `P_i` has length
`L_i + l_i − 1`, and its ratio to the optimal tour is exactly `(L_i + l_i − 1)/n` with
`n = 2^(i+1) − 1`. -/
theorem gbar_ratio_exact (i : ℕ) (hi : 1 ≤ i) (τ : Equiv.Perm (Fin (numNodes i)))
(hτ : ∀ k : Fin (numNodes i), (τ k : ℕ) = (pathP i).getD k 0) :
tourLength (gbar i) τ = pathLength i + ell i - 1 ∧
tourLength (gbar i) τ / optimal (gbar i) =
(pathLength i + ell i - 1) / ((2 : ℝ) ^ (i + 1) - 1) := by sorry
end TSPHeuristics.NNLower
Source
Rosenkrantz, Stearns, Lewis, An Analysis of Several Heuristics for the Traveling Salesman Problem, SIAM J. Comput. 6(3), 1977, https://doi.org/10.1137/0206041, p. 569, first display
Read-back
What the Lean code literally says, in plain math · claude-opus-5-5
Setting.
- is the number of nodes.
- is the shortest-path distance in the edge list .
- is a recursively defined node list.
- is the recursive sequence , , with .
- is the closed-tour length.
- is the minimum of over all permutations.
Claim. Let be a natural number and a permutation of such that, for every , is the -th entry of (with default if absent). Then both of the following hold:
and
Degenerate cases.
- The case is excluded.
- The permutation is a hypothesis, not a conclusion. If the entries of did not form a permutation, no such would exist and the statement would hold vacuously.
- The second conjunct uses real division. It does not separately assert . Under the convention that division by gives , the equation would still be meaningful if were , whereas the right-hand denominator is at least .
Human review
Confirmed by the mission captain (proposal self-audit).
Confirmed by the moderator at approval.