Hungarian algorithm: Difference between revisions

Revision as of 18:55, 14 March 2021

Revision as of 12:23, 16 March 2021

Line 86:

==Matrix interpretation==

{{Confusing|reason=this performs the algorithm on an example, but the actual algorithm for matrixesmatrices was never discussed before, and does not provide details of the actual algorithm, and also relies on vague approaches such as "drawing" a minimum cover.|date=November 2019}}

Given <math>n</math> workers and tasks, and an <math>n</math>×<math>n</math> matrix containing the cost of assigning each worker to a task, find the cost minimizing assignment.

Line 102 ⟶ 103:

'''Step 1'''

Then we perform row operations on the matrix. To do this, '''the lowest of all ''a_i'' '''(i belonging to 1-4)''' is taken and is subtracted from each element in that row.''' ''This will lead to at least one zero in that row'' (We get multiple zeros when there are two equal elements which also happen to be the lowest in that row). '''This procedure is repeated for all rows'''. ''We now have a matrix with at least one zero per row. Now we try to assign tasks to agents such that each agent is doing only one task and the penalty incurred in each case is zero. This is illustrated below.

''

As there are <math>n</math> workers and <math>n</math> tasks, adding or subtracting a fixed number to each item in a row or a column will only change the cost of the assignment by that amount; but the minimum cost assignment under old weights will remain a minimum cost assignment under new weights.

Now we try to assign tasks to agents such that each agent is doing only one task and the penalty incurred in each case is zero. As all weights are non-negative, the assignment will be of minimum cost. This is illustrated below.

:{|class="wikitable" style="text-align:center"

Line 133 ⟶ 139:

In the above case, no assignment can be made. Note that task 1 is done efficiently by both agent a and c. Both can't be assigned the same task. Also note that no one does task 3 efficiently.

To overcome this, we repeat the above procedure for all columns (i.e. '''the minimum element in each column is subtracted from all the elements in that column''') and then check if an assignment is possible.

In most situations this will give the result, but if it is still not possible then we need to keep going.

Line 139 ⟶ 145:

'''Step 3'''

'''All zeros in the matrix must be covered by marking as few rows and/or columns as possible.''' The following procedure is ''one way'' to accomplish this:

First, assign as many tasks as possible.

Line 202 ⟶ 208:

|}

The aforementioned detailed description is ''just one way'' to draw the minimum number of lines to cover all the 0s. Other methods work as well.

'''Step 4'''

'''From the elements that are left, find the lowest value. Subtract this from every unmarked element and add it to every element covered by two lines.'''

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

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.

Basically you find the second minimum cost among the remaining choices. The procedure is repeated until you are able to distinguish among the workers in terms of least cost.

==Bibliography==