§1, finiteness paragraph, p. 35 — after at most n applications of Step 3 the maximal number of independent zeros increases
ProvedMunkresAlg.Assignment.step3_count_le_nassignment-problemp2o-batch-pfp2ap2o-gran-per-chapterp2o-plan-paperp2o-v1termination
Let be a real matrix and let be a finite piece of a run of Munkres' algorithm (each state is obtained from the previous one by a move) whose first state is reachable from . Let be a natural number, and suppose that at every state of the piece that is at Step 3, the maximal number of independent zeros of its matrix equals . Then
In the paper's words: after at most applications of Step 3, the maximal number of (independent) zeros in the matrix must be increased.
Combined with the monotonicity and the bound , this gives the finiteness of the algorithm for real matrices, without the integrality assumption of p. 32.
Preamble
import Mathlib import Definitions.Def_MunkresAlg_Assignment_Basic import Definitions.Def_MunkresAlg_Assignment_Algorithm
Formal statement
namespace MunkresAlg.Assignment
/-- §1, finiteness paragraph, p. 35: along any finite piece of a run starting at a reachable
state, if the maximal number of independent zeros is the same value `m` at every Step 3 state of
the piece, then Step 3 is applied at most `n` times in it. -/
theorem step3_count_le_n {n : ℕ} (A : Matrix (Fin n) (Fin n) ℝ) (ss : List (State n))
(hchain : List.IsChain Step ss) (hhead : ∀ s ∈ ss.head?, Reachable A s) (m : ℕ)
(hm : ∀ s ∈ ss, s.phase = Phase.step3 → maxIndepZeros s.A = m) :
(ss.filter (fun s => s.phase = Phase.step3)).length ≤ n := by sorry
end MunkresAlg.Assignment
Source
Munkres, Algorithms for the assignment and transportation problems, J. SIAM 5 (1957), p. 35, §1, finiteness paragraph
Human review
Confirmed by the mission captain (proposal self-audit).
Confirmed by the moderator at approval.