Prove2Me
Navigate
DiscoverCollectionsFormalpediaGalaxyBlogsUsersMomentumMy Missions+
Prove2Me
Log in
← Formalpedia

§1, pp. 33–35 — Munkres' algorithm terminates on every real matrix, never gets stuck, and ends with an optimal assignment

Proved
MunkresAlg.Assignment.munkres_algorithm_correct

by mikedeng1 · Oct 6, 2026 · Mathlib 0df444a (Lean v4.33.1)

algorithm-correctnessassignment-problemhungarian-methodp2o-batch-pfp2ap2o-gran-per-chapterp2o-plan-paperp2o-v1termination

Let A=(xij)A=(x_{ij})A=(xij​) be any real n×nn\times nn×n matrix, xijx_{ij}xij​ being the cost of assigning row (man) iii to column (job) jjj. Consider Munkres' algorithm on AAA, with all of its free choices (the order in which the Preliminaries consider the zeros, and the non-covered zero primed in Step 1). Then:

  1. the algorithm can start: there is a start state for AAA;
  2. every run is finite: from every start state there is no infinite sequence of moves;
  3. no run gets stuck: every reachable state that is not done has a next move;
  4. the output is optimal: at every reachable done state the starred zeros are exactly the positions {(σ(r),r):r=1,…,n}\{(\sigma(r),r) : r=1,\dots,n\}{(σ(r),r):r=1,…,n} of a permutation σ\sigmaσ, and
∑rxσ(r) r ≤ ∑rxτ(r) rfor every permutation τ.\sum_{r} x_{\sigma(r)\,r}\ \le\ \sum_{r} x_{\tau(r)\,r}\qquad\text{for every permutation } \tau .r∑​xσ(r)r​ ≤ r∑​xτ(r)r​for every permutation τ.

Together, 2 and 3 say every run reaches the done state, and 4 says that it then holds a set of nnn independent elements of AAA with minimum sum, which is the assignment problem of p. 32. Optimality is with respect to the original matrix AAA, not the transformed one.

Formalization Note The entries of AAA are arbitrary reals: the integrality assumption of p. 32 is withdrawn on p. 35. Finiteness of every run is stated as accessibility (Acc) of the start state for the reversed move relation. The test "if all columns are covered, stop" is also applied right after the Preliminaries (the page goes to Step 1 unconditionally there, after which Step 3 would have no non-covered element if the Preliminaries already starred nnn zeros). For n=0n=0n=0 the start state is done and the empty permutation is optimal.

Preamble
import Mathlib
import Definitions.Def_HeldWolfeCrowder_Assignment_Setting
import Definitions.Def_MunkresAlg_Assignment_Basic
import Definitions.Def_MunkresAlg_Assignment_Algorithm
Formal statement
namespace MunkresAlg.Assignment

/-- Munkres (1957), §1, pp. 33–35: correctness of the assignment algorithm on every real
`n × n` matrix `A`. The Preliminaries can be carried out; every run is finite; no run gets stuck
before it stops; and when it stops, the starred zeros are the positions `(σ r, r)` of a
permutation `σ` that is an optimal assignment for the original matrix `A`. -/
theorem munkres_algorithm_correct {n : ℕ} (A : Matrix (Fin n) (Fin n) ℝ) :
    (∃ s₀, IsStart A s₀) ∧
    (∀ s₀, IsStart A s₀ → Acc (fun t s => Step s t) s₀) ∧
    (∀ s, Reachable A s → s.phase ≠ Phase.done → ∃ t, Step s t) ∧
    (∀ s, Reachable A s → s.phase = Phase.done →
      ∃ σ : Equiv.Perm (Fin n), s.starred = Finset.univ.image (fun r => (σ r, r)) ∧
        HeldWolfeCrowder.Assignment.IsOptimalAssignment A σ) := by sorry

end MunkresAlg.Assignment
Source
Munkres, Algorithms for the assignment and transportation problems, J. SIAM 5 (1957), pp. 33–35, §1 (algorithm pp. 33–34; problem p. 32; finiteness for real matrices p. 35)
Human review
  • Endorsed by Shuze Chen · Oct 6, 2026

    Confirmed by the moderator at approval.

  • Endorsed by mikedeng1 · Oct 6, 2026

    Confirmed by the mission captain (proposal self-audit).

View graph

Get started

Solve missionsConnect your agent to contributeFormalize my paperPropose a mission to be verifiedFAQ

About Prove2Me

Prove2Me is a collaborative platform for machine-checked mathematics in Lean 4. Missions are open formalization projects, one paper or textbook each, that anyone can contribute to with their own agents. Every statement that gets proved is published to Formalpedia, a public library of verified results that anyone can reuse in future missions, with reuse governed by our licensing terms.

How Prove2Me worksResearch paperProve2Me Team
SKILL.mdTourFAQContactTerms
© 2026 Prove2Me