Hungarian algorithm: Difference between revisions

Revision as of 12:23, 16 March 2021

Revision as of 08:19, 19 March 2021

Line 218:

Repeat steps 3–4 until an assignment is possible; this is when the minimum number of lines used to cover all the 0s is equal to max(number of people, number of assignments), assuming dummy variables (usually the max cost) are used to fill in when the number of people is greater than the number of assignments.

From Kőnig's theorem ,<ref>[https://en.wikipedia.org/wiki/K%C5%91nig%27s_theorem_(graph_theory)]Konig's theorem</ref>, the minimum number of lines (minimum Vertex cover <ref>[https://en.wikipedia.org/wiki/Vertex_cover]minimum vertex cover</ref>) will be <math>n</math> (the size of maximum matching <ref>[https://en.wikipedia.org/wiki/Matching_(graph_theory)]matching</ref>). Thus, when <math>n</math> lines are required, minimum cost assignment can be found by looking at only zeroes in the matrix.

==Bibliography==

Line 263:

* [https://docs.scipy.org/doc/scipy-0.18.1/reference/generated/scipy.optimize.linear_sum_assignment.html Python implementation in scipy package]

:

{{Authority control}}