Hungarian algorithm: Difference between revisions

Revision as of 08:19, 19 March 2021

Revision as of 01:47, 4 May 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_27s theorem (graph_theorygraph theory)]] Konig's theorem</ref> the minimum number of lines (minimum Vertex cover <ref>[https://en.wikipedia.org/wiki/Vertex_cover[Vertex cover]] minimum vertex cover</ref>) will be <math>n</math> (the size of maximum matching <ref>[https://en.wikipedia.org/wiki/Matching_[Matching (graph_theorygraph 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 262:

* [https://github.com/addaleax/munkres-js Node.js implementation on GitHub]

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

{{Authority control}}