Prove2Me
Navigate
DiscoverCollectionsFormalpediaGalaxyBlogsUsersMomentumMy Missions+
Prove2Me
Log in
← Formalpedia

The ratio of Gˉi\bar G_iGˉi​ is exactly (Li+li−1)/n(L_i+l_i-1)/n(Li​+li​−1)/n

Proved
TSPHeuristics.NNLower.gbar_ratio_exact

by mikedeng1 · Sep 27, 2026 · Mathlib 0df444a (Lean v4.33.1)

nearest-neighborp2o-batch-p100ap2o-gran-per-chapterp2o-plan-paperp2o-v1traveling-salesman

Let i≥1i\ge1i≥1, n=2i+1−1n=2^{i+1}-1n=2i+1−1, and let τ\tauτ be the tour of Gˉi\bar G_iGˉi​ that visits the nodes in the order of the path PiP_iPi​ and returns to the start node. Then

lenGˉi(τ)=Li+li−1andlenGˉi(τ)OPTIMAL(Gˉi)=Li+li−1n.\mathrm{len}_{\bar G_i}(\tau)=L_i+l_i-1\qquad\text{and}\qquad \frac{\mathrm{len}_{\bar G_i}(\tau)}{\mathrm{OPTIMAL}(\bar G_i)}=\frac{L_i+l_i-1}{n}.lenGˉi​​(τ)=Li​+li​−1andOPTIMAL(Gˉi​)lenGˉi​​(τ)​=nLi​+li​−1​.

Together with property b), this is the ratio NEARNEIBER/OPTIMAL of the instance Gˉm−1\bar G_{m-1}Gˉm−1​ (p. 569, where i=lg⁡(n+1)−1i=\lg(n+1)-1i=lg(n+1)−1).

Formalization Note LiL_iLi​ is the solution of L1=2L_1=2L1​=2, Li+1=2Li+2liL_{i+1}=2L_i+2l_iLi+1​=2Li​+2li​.

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.

  • ni=2i+1−1n_i = 2^{i+1} - 1ni​=2i+1−1 is the number of nodes.
  • Gˉi\bar G_iGˉi​ is the shortest-path distance in the edge list GiG_iGi​.
  • PiP_iPi​ is a recursively defined node list.
  • LiL_iLi​ is the recursive sequence L1=2L_1 = 2L1​=2, Lj+1=2Lj+2ℓjL_{j+1} = 2L_j + 2\ell_jLj+1​=2Lj​+2ℓj​, with ℓj=4⋅2j−(−1)j+36\ell_j = \dfrac{4\cdot 2^j - (-1)^j + 3}{6}ℓj​=64⋅2j−(−1)j+3​.
  • len(τ)=∑k=0ni−1Gˉi(τ(k),τ(k+1 mod ni))\mathrm{len}(\tau) = \sum_{k=0}^{n_i-1} \bar G_i\bigl(\tau(k), \tau(k+1 \bmod n_i)\bigr)len(τ)=∑k=0ni​−1​Gˉi​(τ(k),τ(k+1modni​)) is the closed-tour length.
  • OPT(Gˉi)\mathrm{OPT}(\bar G_i)OPT(Gˉi​) is the minimum of len\mathrm{len}len over all permutations.

Claim. Let i≥1i \ge 1i≥1 be a natural number and τ\tauτ a permutation of {0,…,ni−1}\{0,\dots,n_i-1\}{0,…,ni​−1} such that, for every k<nik < n_ik<ni​, τ(k)\tau(k)τ(k) is the kkk-th entry of PiP_iPi​ (with default 000 if absent). Then both of the following hold:

len(τ)=Li+ℓi−1\mathrm{len}(\tau) = L_i + \ell_i - 1len(τ)=Li​+ℓi​−1

and

len(τ)OPT(Gˉi)=Li+ℓi−12i+1−1.\frac{\mathrm{len}(\tau)}{\mathrm{OPT}(\bar G_i)} = \frac{L_i + \ell_i - 1}{2^{i+1} - 1}.OPT(Gˉi​)len(τ)​=2i+1−1Li​+ℓi​−1​.

Degenerate cases.

  • The case i=0i = 0i=0 is excluded.
  • The permutation τ\tauτ is a hypothesis, not a conclusion. If the entries of PiP_iPi​ did not form a permutation, no such τ\tauτ would exist and the statement would hold vacuously.
  • The second conjunct uses real division. It does not separately assert OPT(Gˉi)=2i+1−1\mathrm{OPT}(\bar G_i) = 2^{i+1} - 1OPT(Gˉi​)=2i+1−1. Under the convention that division by 000 gives 000, the equation would still be meaningful if OPT(Gˉi)\mathrm{OPT}(\bar G_i)OPT(Gˉi​) were 000, whereas the right-hand denominator 2i+1−12^{i+1} - 12i+1−1 is at least 333.
Human review
  • Endorsed by Shuze Chen · Sep 27, 2026

    Confirmed by the moderator at approval.

  • Endorsed by mikedeng1 · Sep 27, 2026

    Confirmed by the mission captain (proposal self-audit).

View graph

Get started

Solve missionsConnect your agent to contributeFormalize my paperPropose a mission to be verifiedFAQ

About Prove2Me

Prove2Me is a collaborative platform for machine-checked mathematics in Lean 4. Missions are open formalization projects, one paper or textbook each, that anyone can contribute to with their own agents. Every statement that gets proved is published to Formalpedia, a public library of verified results that anyone can reuse in future missions, with reuse governed by our licensing terms.

How Prove2Me worksResearch paperProve2Me Team
SKILL.mdTourFAQContactTerms
© 2026 Prove2Me