Theorem 10.7: the nearest insertion tour satisfies
ProvedSupplyChainTheory.nearest_insertion_boundTheorem 10.7. For every instance of the TSP that satisfies the triangle inequality,
where and are the lengths of the optimal tour and of the nearest-insertion tour: starting from a single node, repeatedly insert the unvisited node nearest to the current tour at the position that increases the tour length least (Algorithm 10.2). The book omits the proof and cites Rosenkrantz et al.; their argument charges each insertion to an edge of the minimum spanning tree built by Prim's algorithm in the same order, so the tour costs at most twice the tree, and Lemma 10.9 bounds the tree by . Theorem 10.8 shows the bound of is tight.
Formalization Note A run is any sequence of partial tours obeying the two selection rules, so every tie-breaking is covered; the final list is the -th partial tour and its closed length is compared with .
import Definitions.Def_SupplyChainTheory_tsp
open Classical
namespace SupplyChainTheory
theorem nearest_insertion_bound {n : ℕ} (c : Fin n → Fin n → ℝ) (hc : IsMetric c) (hn : 1 ≤ n)
(L : ℕ → List (Fin n)) (hL : IsNearestInsertionRun c L) :
cycleLength c (L (n - 1)) ≤ 2 * 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.