§1, Remark (2), p. 33 — replacing x_ij by x_ij − u_i − v_j does not change the optimal assignments
ProvedMunkresAlg.Assignment.remark_2_reductionassignment-problemoptimal-assignmentp2o-batch-pfp2ap2o-gran-per-chapterp2o-plan-paperp2o-v1reduction
Let be a real matrix and let and be arbitrary real constants. Put . For an assignment given by a permutation of , where is the row assigned to column , write . Then for every permutation ,
That is, the solution of the assignment problem is not changed by subtracting constants from rows and columns.
This is the reason every matrix transformation of the algorithm (row and column reductions, and Step 3) preserves the solution: the final starred zeros are optimal for the original matrix.
Preamble
import Mathlib import Definitions.Def_HeldWolfeCrowder_Assignment_Setting
Formal statement
namespace MunkresAlg.Assignment
/-- Munkres (1957), §1, Remark (2), p. 33: subtracting arbitrary row constants `u i` and column
constants `v j` from the matrix does not change the set of optimal assignments. -/
theorem remark_2_reduction {n : ℕ} (A : Matrix (Fin n) (Fin n) ℝ) (u v : Fin n → ℝ)
(σ : Equiv.Perm (Fin n)) :
HeldWolfeCrowder.Assignment.IsOptimalAssignment A σ ↔
HeldWolfeCrowder.Assignment.IsOptimalAssignment (fun i j => A i j - u i - v j) σ := by sorry
end MunkresAlg.Assignment
Source
Munkres, Algorithms for the assignment and transportation problems, J. SIAM 5 (1957), p. 33, §1, Remark (2)
Human review
Confirmed by the mission captain (proposal self-audit).
Confirmed by the moderator at approval.