Theorem 10.6 (first part): the nearest neighbor tour satisfies
ProvedSupplyChainTheory.nearest_neighbor_boundTheorem 10.6, first part. Consider an -node instance of the TSP satisfying the triangle inequality, and let and 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
The book omits the proof and cites Rosenkrantz, Stearns and Lewis (1977). The bound grows with , and the theorem's second part, that instances exist with ratio exceeding , shows no constant bound is possible; that part is an existence claim about specific instances and is not formalized here.
Formalization Note 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.
import Definitions.Def_SupplyChainTheory_tsp
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
Confirmed by the mission captain (proposal self-audit).
Confirmed by the moderator at approval.
Confirmed by the moderator at approval.