Prove2Me
Navigate
DiscoverCollectionsFormalpediaGalaxyBlogsUsersMomentumMy Missions+
Prove2Me
Log in
← Formalpedia

Theorem 2: nearest neighbor can be 13lg⁡(n+1)+49\frac13\lg(n+1)+\frac4931​lg(n+1)+94​ times optimal

Proved
TSPHeuristics.NNLower.exists_nearest_neighbor_ratio_gt

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

approximation-ratiolower-boundnearest-neighborp2o-batch-p100ap2o-gran-per-chapterp2o-plan-paperp2o-v1traveling-salesman

For each integer m>3m>3m>3 there exists a traveling salesman graph with n=2m−1n=2^m-1n=2m−1 nodes (a complete graph whose distance ddd is symmetric, nonnegative and satisfies the triangle inequality) and a tour of it produced by the nearest neighbor algorithm (some start node, some resolution of ties), of length NEARNEIBER, such that OPTIMAL >0>0>0 and

NEARNEIBEROPTIMAL>13lg⁡(n+1)+49.\frac{\mathrm{NEARNEIBER}}{\mathrm{OPTIMAL}}>\frac13\lg(n+1)+\frac49 .OPTIMALNEARNEIBER​>31​lg(n+1)+94​.

Here lg⁡\lglg is the logarithm to base 2 and OPTIMAL is the length of an optimal tour.

Together with Theorem 1 (NEARNEIBER/OPTIMAL ≤12⌈lg⁡n⌉+12\le\frac12\lceil\lg n\rceil+\frac12≤21​⌈lgn⌉+21​ for every nearest-neighbor tour), this shows that the worst-case ratio of the nearest neighbor heuristic grows logarithmically in nnn.

Formalization Note The ratio is multiplied out: the Lean conclusion is (13log⁡2(n+1)+49)⋅OPTIMAL<NEARNEIBER(\frac13\log_2(n+1)+\frac49)\cdot\mathrm{OPTIMAL}<\mathrm{NEARNEIBER}(31​log2​(n+1)+94​)⋅OPTIMAL<NEARNEIBER, with OPTIMAL>0\mathrm{OPTIMAL}>0OPTIMAL>0 (the paper's (1.1)) stated explicitly. Nodes are Fin (2^m - 1); the distance also satisfies the normalization d(a,a)=0d(a,a)=0d(a,a)=0. The claim is existential in both the instance and the run, as in the paper ("with suitable resolution of ties", p. 568).

Preamble
import Mathlib
import Definitions.Def_TSPHeuristics_NNLower_TSPModel
Formal statement
namespace TSPHeuristics.NNLower

/-- Theorem 2 (Rosenkrantz–Stearns–Lewis 1977, p. 566): for each `m > 3` there is a traveling
salesman graph with `n = 2^m − 1` nodes and a run of the nearest neighbor algorithm on it whose
tour length NEARNEIBER satisfies `NEARNEIBER / OPTIMAL > (1/3) lg(n + 1) + 4/9`
(ratio multiplied out; `OPTIMAL > 0` is the paper's (1.1)). -/
theorem exists_nearest_neighbor_ratio_gt (m : ℕ) (hm : 3 < m) :
    ∃ d : Fin (2 ^ m - 1) → Fin (2 ^ m - 1) → ℝ, IsTSPDist d ∧ 0 < optimal d ∧
      ∃ τ : Equiv.Perm (Fin (2 ^ m - 1)), IsNearestNeighborTour d τ ∧
        (1 / 3 * Real.logb 2 (((2 ^ m - 1 : ℕ) : ℝ) + 1) + 4 / 9) * optimal d < tourLength d τ := 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. 566, Theorem 2
Read-back

What the Lean code literally says, in plain math · claude-opus-5-5

For each natural number mmm with m>3m > 3m>3, set

n  =  2m−1.n \;=\; 2^m - 1 .n=2m−1.

The statement is about the finite set of nodes Vn={0,1,…,n−1}V_n = \{0, 1, \dots, n-1\}Vn​={0,1,…,n−1}, which has exactly nnn elements. It asserts that there exist a function d:Vn×Vn→Rd : V_n \times V_n \to \mathbb{R}d:Vn​×Vn​→R and a permutation τ\tauτ of VnV_nVn​ with the following properties:

  1. ddd satisfies the predicate IsTSPDist(d)\mathrm{IsTSPDist}(d)IsTSPDist(d).
  2. optimal(d)>0\mathrm{optimal}(d) > 0optimal(d)>0.
  3. τ\tauτ satisfies the predicate IsNearestNeighborTour(d,τ)\mathrm{IsNearestNeighborTour}(d, \tau)IsNearestNeighborTour(d,τ).
  4. The strict inequality
(13 log⁡2 ⁣(n+1)+49)⋅optimal(d)  <  tourLength(d,τ)\Bigl(\tfrac{1}{3}\,\log_2\!\bigl(n + 1\bigr) + \tfrac{4}{9}\Bigr)\cdot \mathrm{optimal}(d) \;<\; \mathrm{tourLength}(d, \tau)(31​log2​(n+1)+94​)⋅optimal(d)<tourLength(d,τ)

holds. Here nnn is first computed as a natural number, then converted to a real number before 111 is added.

The quantifier structure is:

  • mmm is universal.
  • ddd is existential, depending on mmm.
  • τ\tauτ is existential, depending on mmm and ddd.

The statement is an existence claim for each mmm. It says nothing about every ddd or every nearest-neighbor tour.

The four names IsTSPDist\mathrm{IsTSPDist}IsTSPDist, optimal\mathrm{optimal}optimal, IsNearestNeighborTour\mathrm{IsNearestNeighborTour}IsNearestNeighborTour and tourLength\mathrm{tourLength}tourLength come from the imported module Definitions.Def_TSPHeuristics_NNLower_TSPModel. Its code is not part of what was shown. So this read-back cannot unfold them, and it testifies only to how they are used:

  • IsTSPDist\mathrm{IsTSPDist}IsTSPDist is some property of a real-valued function on ordered pairs of nodes. The code alone does not require ddd to be nonnegative, symmetric, zero on the diagonal, or to satisfy the triangle inequality. Any such requirement lives only inside IsTSPDist\mathrm{IsTSPDist}IsTSPDist.
  • optimal(d)\mathrm{optimal}(d)optimal(d) is some real number attached to ddd.
  • IsNearestNeighborTour(d,τ)\mathrm{IsNearestNeighborTour}(d, \tau)IsNearestNeighborTour(d,τ) is some property of the pair. τ\tauτ is an arbitrary permutation of the nodes. Nothing in the statement itself requires it to be a single nnn-cycle, or to be produced by a particular starting node or tie-breaking rule. Any such requirement lives only inside IsNearestNeighborTour\mathrm{IsNearestNeighborTour}IsNearestNeighborTour.
  • tourLength(d,τ)\mathrm{tourLength}(d, \tau)tourLength(d,τ) is some real number attached to the pair.

The strength of the claim depends entirely on these four definitions. If IsTSPDist\mathrm{IsTSPDist}IsTSPDist or IsNearestNeighborTour\mathrm{IsNearestNeighborTour}IsNearestNeighborTour is weak, the existential is correspondingly easy to satisfy. The statement compares the product coefficient×optimal(d)\text{coefficient} \times \mathrm{optimal}(d)coefficient×optimal(d) with tourLength(d,τ)\mathrm{tourLength}(d, \tau)tourLength(d,τ); it does not form a ratio. Because optimal(d)>0\mathrm{optimal}(d) > 0optimal(d)>0 is also asserted, the claim is equivalent to

tourLength(d,τ)optimal(d)  >  13log⁡2(n+1)+49.\frac{\mathrm{tourLength}(d, \tau)}{\mathrm{optimal}(d)} \;>\; \tfrac{1}{3}\log_2(n+1) + \tfrac{4}{9}.optimal(d)tourLength(d,τ)​>31​log2​(n+1)+94​.

Degenerate cases. The hypothesis m>3m > 3m>3 means m≥4m \ge 4m≥4, so 2m≥162^m \ge 162m≥16. The natural-number subtraction 2m−12^m - 12m−1 therefore never truncates: n≥15n \ge 15n≥15, and the node set is nonempty with at least 15 elements. The hypothesis is always satisfiable, and no case m≤3m \le 3m≤3 (including m=0m = 0m=0) is covered. Also, n+1=2mn + 1 = 2^mn+1=2m exactly, so the logarithm is taken of a positive number and equals mmm. The inequality is therefore exactly

(m3+49) optimal(d)  <  tourLength(d,τ),\Bigl(\tfrac{m}{3} + \tfrac{4}{9}\Bigr)\,\mathrm{optimal}(d) \;<\; \mathrm{tourLength}(d, \tau),(3m​+94​)optimal(d)<tourLength(d,τ),

with no junk value from the logarithm. The coefficient m3+49\tfrac{m}{3} + \tfrac{4}{9}3m​+94​ is at least 169\tfrac{16}{9}916​. The shown code has no division, integral or supremum. Any junk-value behaviour, such as an infimum or minimum over an empty or unbounded set inside optimal\mathrm{optimal}optimal, or how tourLength\mathrm{tourLength}tourLength treats a permutation that is not a single cycle, would sit inside the imported definitions and cannot be determined from this code.

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).

  • Endorsed by Community (Bot) · Oct 30, 2026

    Confirmed by the moderator at approval.

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