§1, the stronger result, p. 35 — if n_{k+1} = n_k, Step 2 does not occur and Step 3 is begun with more horizontal covered lines
ProvedMunkresAlg.Assignment.stronger_resultassignment-probleminvariantp2o-batch-pfp2ap2o-gran-per-chapterp2o-plan-paperp2o-v1termination
Let be a real matrix, let be a state reachable by Munkres' algorithm from that is at Step 3 with matrix , and let be the state after the Step 3 move, with matrix . Suppose , where is the maximal number of independent zeros of . Let be any state reached from by moves made in Step 1 such that is no longer in Step 1. Then
- is at Step 3 (Step 2 does not occur), and
- every covered row of is a covered row of , and
Covered rows are the paper's horizontal covered lines. This is the progress measure that replaces the integrality assumption in the proof of finiteness.
Preamble
import Mathlib import Definitions.Def_MunkresAlg_Assignment_Basic import Definitions.Def_MunkresAlg_Assignment_Algorithm
Formal statement
namespace MunkresAlg.Assignment
/-- §1, the stronger result, p. 35: if the Step 3 transformation from `A_k = s.A` to
`A_{k+1} = s₁.A` leaves the maximal number of independent zeros unchanged, then every way of
continuing Step 1 from `s₁` until Step 1 is left goes to Step 3 (Step 2 does not occur), and
Step 3 is begun with more covered rows (horizontal lines) than at `s`, every covered row of `s`
still being covered. -/
theorem stronger_result {n : ℕ} (A : Matrix (Fin n) (Fin n) ℝ) (s s₁ : State n)
(hs : Reachable A s) (hph : s.phase = Phase.step3) (h1 : Step s s₁)
(heq : maxIndepZeros s₁.A = maxIndepZeros s.A) :
∀ s₂ : State n, Relation.ReflTransGen Step1Move s₁ s₂ → s₂.phase ≠ Phase.step1 →
s₂.phase = Phase.step3 ∧ s.rowCov ⊆ s₂.rowCov ∧ s.rowCov.card < s₂.rowCov.card := by sorry
end MunkresAlg.Assignment
Source
Munkres, Algorithms for the assignment and transportation problems, J. SIAM 5 (1957), p. 35, §1, the stronger result
Human review
Confirmed by the mission captain (proposal self-audit).
Confirmed by the moderator at approval.