Theorem 10.11: the minimum spanning tree heuristic satisfies
ProvedSupplyChainTheory.mst_heuristic_boundTheorem 10.11. For every instance of the TSP that satisfies the triangle inequality,
where is the length of the tour returned by the minimum spanning tree heuristic (Algorithm 10.5): find an MST , double its edges, take an Eulerian tour of the result, and shortcut it by visiting the nodes in order of first appearance. The Eulerian tour has length by Lemma 10.9, and shortcutting replaces paths by edges , which by the triangle inequality can only shorten it.
Formalization Note The doubled tree is represented by a closed walk in the tree that traverses each tree edge exactly twice, and the heuristic's tour is any shortcut of it; every Eulerian tour of the doubled tree and every choice of start node is covered.
import Definitions.Def_SupplyChainTheory_tsp
open Classical
namespace SupplyChainTheory
theorem mst_heuristic_bound {n : ℕ} (c : Fin n → Fin n → ℝ) (hc : IsMetric c) (hn : 1 ≤ n)
(T : SimpleGraph (Fin n)) (hT : IsMST c T) (v : Fin n) (W : T.Walk v v)
(hW : ∀ e ∈ T.edgeSet, W.edges.count e = 2) (τ : Equiv.Perm (Fin n))
(hτ : IsShortcut W.support τ) :
tourLength c τ ≤ 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.