Theorem 2: nearest neighbor can be times optimal
ProvedTSPHeuristics.NNLower.exists_nearest_neighbor_ratio_gtFor each integer there exists a traveling salesman graph with nodes (a complete graph whose distance 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 and
Here is the logarithm to base 2 and OPTIMAL is the length of an optimal tour.
Together with Theorem 1 (NEARNEIBER/OPTIMAL for every nearest-neighbor tour), this shows that the worst-case ratio of the nearest neighbor heuristic grows logarithmically in .
Formalization Note The ratio is multiplied out: the Lean conclusion is , with (the paper's (1.1)) stated explicitly. Nodes are Fin (2^m - 1); the distance also satisfies the normalization . The claim is existential in both the instance and the run, as in the paper ("with suitable resolution of ties", p. 568).
import Mathlib import Definitions.Def_TSPHeuristics_NNLower_TSPModel
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
Read-back
What the Lean code literally says, in plain math · claude-opus-5-5
For each natural number with , set
The statement is about the finite set of nodes , which has exactly elements. It asserts that there exist a function and a permutation of with the following properties:
- satisfies the predicate .
- .
- satisfies the predicate .
- The strict inequality
holds. Here is first computed as a natural number, then converted to a real number before is added.
The quantifier structure is:
- is universal.
- is existential, depending on .
- is existential, depending on and .
The statement is an existence claim for each . It says nothing about every or every nearest-neighbor tour.
The four names , , and 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:
- is some property of a real-valued function on ordered pairs of nodes. The code alone does not require to be nonnegative, symmetric, zero on the diagonal, or to satisfy the triangle inequality. Any such requirement lives only inside .
- is some real number attached to .
- is some property of the pair. is an arbitrary permutation of the nodes. Nothing in the statement itself requires it to be a single -cycle, or to be produced by a particular starting node or tie-breaking rule. Any such requirement lives only inside .
- is some real number attached to the pair.
The strength of the claim depends entirely on these four definitions. If or is weak, the existential is correspondingly easy to satisfy. The statement compares the product with ; it does not form a ratio. Because is also asserted, the claim is equivalent to
Degenerate cases. The hypothesis means , so . The natural-number subtraction therefore never truncates: , and the node set is nonempty with at least 15 elements. The hypothesis is always satisfiable, and no case (including ) is covered. Also, exactly, so the logarithm is taken of a positive number and equals . The inequality is therefore exactly
with no junk value from the logarithm. The coefficient is at least . 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 , or how treats a permutation that is not a single cycle, would sit inside the imported definitions and cannot be determined from this code.
Confirmed by the mission captain (proposal self-audit).
Confirmed by the moderator at approval.
Confirmed by the moderator at approval.