§1, Step D (p. 33) for Step 3 — the sum of the elements decreases by n(n − n_k)h
ProvedMunkresAlg.Assignment.step3_sum_decreaseassignment-problemdual-updatep2o-batch-pfp2ap2o-gran-per-chapterp2o-plan-paperp2o-v1
Let be a real matrix and let be a state reachable by Munkres' algorithm from that is at Step 3, with matrix . Let be the smallest non-covered element of , and let be a state reached from by the Step 3 move, with matrix . With the maximal number of independent zeros of ,
Step 3 is the transformation of Step C of Flood's outline, and Step D states this decrease; for integer matrices it gives the original finiteness argument.
Formalization Note is computed in the reals; it is non-negative because .
Preamble
import Mathlib import Definitions.Def_MunkresAlg_Assignment_Basic import Definitions.Def_MunkresAlg_Assignment_Algorithm
Formal statement
namespace MunkresAlg.Assignment
/-- §1, Step D (p. 33) for the transformation of Step 3: the sum of the elements of the matrix
decreases by `n (n − n_k) h`, where `n_k` is the maximal number of independent zeros before the
transformation and `h` the smallest non-covered element. -/
theorem step3_sum_decrease {n : ℕ} (A : Matrix (Fin n) (Fin n) ℝ) (s t : State n) (h : ℝ)
(hs : Reachable A s) (hph : s.phase = Phase.step3)
(hmin : ∃ p, NonCovered s p ∧ s.A p.1 p.2 = h) (hle : ∀ q, NonCovered s q → h ≤ s.A q.1 q.2)
(hst : Step s t) :
∑ i, ∑ j, t.A i j =
∑ i, ∑ j, s.A i j - (n : ℝ) * ((n : ℝ) - (maxIndepZeros s.A : ℝ)) * h := by sorry
end MunkresAlg.Assignment
Source
Munkres, Algorithms for the assignment and transportation problems, J. SIAM 5 (1957), p. 33, §1, Step D (applied to Step 3, p. 34, which 'is the same transformation as is specified in Step C')
Human review
Confirmed by the mission captain (proposal self-audit).
Confirmed by the moderator at approval.