Lemma 10.16: under , tours gain , optimal tours stay optimal, and a 1-tree gains
ProvedSupplyChainTheory.revised_cost_identitiesheld-karpoperations-researchspanning-treestraveling-salesman
Lemma 10.16. Let and (10.31).
(a) If is a TSP tour, then .
(b) If is an optimal tour under , then it is also optimal under .
(c) For any 1-tree , , where is the degree of node in .
The book omits the proof (Problem 10.15). Every node has degree two in a tour, which gives (a) and hence (b), while a 1-tree's degrees vary, which is why the revision can raise the optimal 1-tree length relative to the tour length and tighten the bound.
Preamble
import Definitions.Def_SupplyChainTheory_tsp
Formal statement
open Classical
namespace SupplyChainTheory
theorem revised_cost_identities {n : ℕ} (c : Fin n → Fin n → ℝ) (hc : IsMetric c) (hn : 3 ≤ n)
(lam : Fin n → ℝ) :
(∀ τ : Equiv.Perm (Fin n), tourLength (revisedCost c lam) τ = tourLength c τ + 2 * ∑ i, lam i)
∧ (∀ τ : Equiv.Perm (Fin n), IsMinOn (tourLength c) Set.univ τ →
IsMinOn (tourLength (revisedCost c lam)) Set.univ τ)
∧ ∀ (r : Fin n) (G : SimpleGraph (Fin n)), Is1Tree r G →
graphWeight (revisedCost c lam) G = graphWeight c G + ∑ i, G.degree i * lam i := 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. 446, Sect. 10.6.1, Lemma 10.16, Eq. (10.31)-(10.32): 'Proof. Omitted; see Problem 10.15'
Human review
Confirmed by the mission captain (proposal self-audit).
Confirmed by the moderator at approval.