Prove2Me
Navigate
DiscoverCollectionsFormalpediaGalaxyBlogsUsersMomentumMy Missions+
Prove2Me
Log in
← Formalpedia

Theorem 10.6 (first part): the nearest neighbor tour satisfies zNN/z∗≤12(⌈log⁡2n⌉+1)z_{NN}/z^* \le \tfrac{1}{2}(\lceil \log_2 n \rceil + 1)zNN​/z∗≤21​(⌈log2​n⌉+1)

Proved
SupplyChainTheory.nearest_neighbor_bound

by naimengye · Sep 24, 2026 · Mathlib 0df444a (Lean v4.33.1)

approximationheuristicsoperations-researchtraveling-salesman

Theorem 10.6, first part. Consider an nnn-node instance of the TSP satisfying the triangle inequality, and let z∗z^*z∗ and zNNz_{NN}zNN​ be the lengths of the optimal tour and of a nearest-neighbor tour, a tour in which every step goes to a nearest unvisited node (Algorithm 10.1, any starting node and any tie-breaking). Then

zNNz∗  ≤  12(⌈log⁡2n⌉+1).\frac{z_{NN}}{z^*} \;\le\; \frac{1}{2}\big(\lceil \log_2 n \rceil + 1\big).z∗zNN​​≤21​(⌈log2​n⌉+1).

The book omits the proof and cites Rosenkrantz, Stearns and Lewis (1977). The bound grows with nnn, and the theorem's second part, that instances exist with ratio exceeding 13(⌈log⁡2(n+1)⌉+43)\frac{1}{3}(\lceil\log_2(n+1)\rceil + \frac{4}{3})31​(⌈log2​(n+1)⌉+34​), shows no constant bound is possible; that part is an existence claim about specific instances and is not formalized here.

Formalization Note ⌈log⁡2n⌉\lceil \log_2 n \rceil⌈log2​n⌉ is Nat.clog 2 n, and the tour is any permutation with the nearest-neighbor property, so all starting nodes and tie-breaks are covered.

Preamble
import Definitions.Def_SupplyChainTheory_tsp
Formal statement
open Classical

namespace SupplyChainTheory

theorem nearest_neighbor_bound {n : ℕ} (c : Fin n → Fin n → ℝ) (hc : IsMetric c) (hn : 1 ≤ n)
    (τ : Equiv.Perm (Fin n)) (hτ : IsNearestNeighborTour c τ) :
    tourLength c τ ≤ (1 / 2 : ℝ) * (Nat.clog 2 n + 1) * optTourLength c := by sorry

end SupplyChainTheory
Source
Lawrence V. Snyder and Zuo-Jun Max Shen, Fundamentals of Supply Chain Theory, 2nd ed., Wiley 2019, DOI 10.1002/9781119584445, p. 418, Sect. 10.4.1, Theorem 10.6, Eq. (10.23): 'Proof. Omitted; see Rosenkrantz et al. (1977)'
Human review
  • Endorsed by Shuze Chen · Sep 25, 2026

    Confirmed by the moderator at approval.

  • Endorsed by naimengye · Sep 25, 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