Weighted blossom matching — program refinement and cubic bound
ProvedVehicleRoutingSurvey.Routing.weightedBlossomMatchingBlock_spec_at_entrygraph-theoryrural-postman
A refinement of the fixed weighted matcher gives the compact matching execution contract with instruction constant 27648.
Preamble
import Definitions.Def_VehicleRoutingSurvey_RuralPostman1979_MatcherProofInterfaces open VehicleRoutingSurvey.Routing SupplyChainTheory
Formal statement
theorem VehicleRoutingSurvey.Routing.weightedBlossomMatchingBlock_spec_at_entry
(refined : ∀ {k : ℕ} {cost : Fin k → Fin k → ℝ} {s : ArithmeticState},
CompactMateInput cost s → s.pc = 0 → s.halted = false → Nonempty (WeightedMatchingRefinement k cost s)) :
CompactMateBlockSpec weightedBlossomMatchingBlock 27648 := by sorrySource
J. K. Lenstra and A. H. G. Rinnooy Kan, Complexity of vehicle routing and scheduling problems (1979), Table 3, printed p. 5. https://ir.cwi.nl/pub/9658/9658D.pdf