Hungarian algorithm: Difference between revisions

Revision as of 10:20, 7 March 2024

Revision as of 16:37, 31 March 2024

Line 337:

==Matrix interpretation==

This variant of the algorithm follows the formulation given by Flood<ref name="flood">{{cite journal | last=Flood | first=Merrill M. | title=The Traveling-Salesman Problem | journal=Operations Research | volume=4 | issue=1 | date=1956 | issn=0030-364X | doi=10.1287/opre.4.1.61 | pages=61–75}}</ref>, and later described more explicitly by Munkres, who proved it runs in <math>\mathcal{O}(n^4)</math> time.<ref name="munkres"/> Instead of keeping track of the potentials of the vertices, the algorithm operates only on a matrix:

Given {{mvar|n}} workers and tasks, the problem is written in the form of an {{mvar|n}}×{{mvar|n}} matrix

:<math>a_{ij}:=c(i,j)-y(i)-y(j)</math>

where <math>c(i,j)</math> is the original cost matrix and <math>y(i), y(j)</math> are the potentials from the graph interpretation. Changing the potentials corresponds to adding or subtracting from rows or columns of this matrix. The algorithm starts with <math>a_{ij} = c(i, j)</math>. As such, it can be viewed as taking the original cost matrix and modifying it.

Given {{mvar|n}} workers and tasks, the problem is written in the form of an {{mvar|n}}×{{mvar|n}} cost matrix

:{{aligned table|cols=4|class=wikitable

Line 416 ⟶ 422:

|}

Find a non-covered zero and prime it{{clarify|what does(mark primeit meanwith herea [[Prime (symbol)|date=Decemberprime 2023}}symbol]]). (If no such zero can be found, meaning all zeroes are covered, skip to step 5.)

* If the zero is on the same row as a starred zero, cover the corresponding row, and uncover the column of the starred zero.

Line 517 ⟶ 523:

===Step 5===

If the number of starred zeros is {{mvar|n}} (or in the general case <math>min(n,m)</math>, where {{mvar|n}} is the number of people and {{mvar|m}} is the number of jobs), the algorithm terminates. See the [[#Result|Result]] subsection below on how to interpret the results.

{{Confusing|section|date=May 2023}}

'''FindOtherwise, find the lowest uncovered value. Subtract this from every unmarked element and add it to every element covered by two lines. Go back to step 4.'''

This is equivalent to subtracting a number from all rows which are not covered and adding the same number to all columns which are covered. These operations do not change optimal assignments.

===Result===

Repeat steps 4–5 until an assignment is possible; this is when the minimum number of lines used to cover all the 0s is equal to min(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.

If following this specific version of the algorithm, the starred zeros form the minimum assignment.

From Kőnig's theorem,<ref>[[K%C5%91nig%27s theorem (graph theory)]] Konig's theorem</ref> the minimum number of lines (minimum vertex cover<ref>[[Vertex cover]] minimum vertex cover</ref>) will be {{mvar|n}} (the size of maximum matching<ref>[[Matching (graph theory)]] matching</ref>). Thus, when {{mvar|n}} lines are required, minimum cost assignment can be found by looking at only zeroes in the matrix.

==Bibliography==

* R.E. Burkard, M. Dell'Amico, S. Martello: ''Assignment Problems'' (Revised reprint). SIAM, Philadelphia (PA.) 2012. {{ISBN|978-1-61197-222-1}}