Lemma 10.15: the optimal 1-tree is a lower bound,
ProvedSupplyChainTheory.one_tree_lower_boundheld-karplower-boundsoperations-researchspanning-treestraveling-salesman
Lemma 10.15. Let be an optimal 1-tree for a TSP instance on nodes, a spanning tree on the nodes other than the root plus two edges incident to the root, of least total length. Then .
Every tour is a 1-tree: removing the root leaves a spanning path on the other nodes, and the root has degree two. So the minimum 1-tree is a relaxation of the TSP, one that is easy to compute (an MST on the other nodes plus the two shortest edges at the root) and that improves on the MST bound by one edge.
Preamble
import Definitions.Def_SupplyChainTheory_tsp
Formal statement
open Classical
namespace SupplyChainTheory
theorem one_tree_lower_bound {n : ℕ} (c : Fin n → Fin n → ℝ) (hc : IsMetric c) (hn : 3 ≤ n)
(r : Fin n) : opt1TreeLength c r ≤ 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. 442, Sect. 10.6.1, Lemma 10.15; after Held and Karp (1970)
Human review
Confirmed by the mission captain (proposal self-audit).
Confirmed by the moderator at approval.