Hungarian algorithm: Difference between revisions

Revision as of 22:14, 8 January 2023

Revision as of 23:35, 11 January 2023

Line 88:

==Matrix interpretation==

Given {{mvar|n}} workers and tasks, andthe problem is written in the form of an {{mvar|n}}×{{mvar|n}} matrix containing the cost of assigning each worker to a task, find the cost minimizing assignment.

First the problem is written in the form of a matrix as given below

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

| a₁ | a₂ | a₃ | a₄

|a1 | a2 | a3 | a4

| b₁ | b₂ | b₃ | b₄

|b1 | b2 | b3 | b4

| c₁ | c₂ | c₃ | c₄

|c1 | c2 | c3 | c4

| d₁ | d₂ | d₃ | d₄}}

|d1 | d2 | d3 | d4}}

where a, b, c and d are the workers who have to perform tasks 1, 2, 3 and 4. a1a₁, a2a₂, a3a₃, a4and a₄ denote the penalties incurred when worker "a" does task 1, 2, 3, and 4 respectively. The same holds true for the other symbols as well. The matrix is square, so each worker can perform only one task.

The problem is equivalent to assigning each worker a unique task such that the total penalty is minimized. Note that each task can only be worked on by one worker.

===Step 1===

'''For each row, its minimum element is subtracted from every element in that row.''' This causes all elements to have non-negative values. Therefore, an assignment with a total penalty of 0 is by definition a minimum assignment.

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.''

This also leads to at least one zero in each row. As such, a naive greedy algorithm can attempt to assign all workers a task with a penalty of zero. This is illustrated below.

As there are {{mvar|n}} workers and {{mvar|n}} 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.

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

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.

| 0 | a₂ | a₃ | a₄

| b₁ | b₂ | b₃ | 0

| c₁ | 0 | c₃ | c₄

| d₁ | d₂ | 0 | d₄}}

The zeros thatabove arewould indicated as 0 arebe the assigned tasks.

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

|-

| 0 ||a2'||a3' ||a4'

|-

|b1'||b2'||b3'|| 0

|-

|c1'|| 0 ||c3'||c4'

|-

|d1'||d2'|| 0 ||d4'

|}

Worst-case there are {{mvar|n}}! combinations to try, since multiple zeroes can appear in a row if multiple elements are the minimum. So at some point this naive algorithm should be short circuited.

The zeros that are indicated as 0 are the assigned tasks.

===Step 2===

Line 125 ⟶ 120:

Sometimes it may turn out that the matrix at this stage cannot be used for assigning, as is the case for the matrix below.

:{{aligned table|cols=4|class="wikitable" style="text-align:center"

| 0 | a₂ | 0 | a₄

|-

| b₁ | 0 | b₃ | 0

| 0 ||a2'|| 0 ||a4'

| 0 | c₂ | c₃ | c₄

|-

| 0 | d₂ | d₃ | d₄}}

|b1'|| 0 ||b3'|| 0

|-

| 0 ||c2'||c3'||c4'

|-

| 0 ||d2'||d3'||d4'

|}

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 with penalty 0 is possible.

In the above case, no assignment can be made. Note that task 1 is done efficiently by both agents c and d. 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 143 ⟶ 132:

===Step 3===

'''All zeros in the matrix must be covered by marking as few rows and/or columns as possible.''' TheSteps following3 procedureand is4 form ''one way'' to accomplish this:.

*FirstFor each row, assigntry asto manyassign tasksan asarbitrary possiblezero. The assignedAssigned tasks are represented by starring a zero. Note that assignments can't be in the same row or column.

** We assign the first zero of Row 1. The second zero of Row 1 can't be assigned, because it is on the same row as the first zero.

** We assign the first zero of Row 2. The second zero of Row 2 can't be assigned.

** Zeros on Row 3 and Row 4 can't be assigned, because they are on the same column as the zero assigned on Row 1.

We could end with another assignment if we choose another ordering of the rows and columns.

:{{aligned table|cols=4|class="wikitable" style="text-align:center"

| 0* | a₂ | 0 | a₄

|-

| b₁ | 0* | b₃ | 0

| 0*||a2'|| 0 ||a4'

| 0 | c₂ | c₃ | c₄

|-

| 0 | d₂ | d₃ | d₄}}

|b1'|| 0*||b3'|| 0

|-

===Step 4===

| 0 ||c2'||c3'||c4'

|-

Cover all columns containing a (starred) zero.

| 0 ||d2'||d3'||d4'

|}

* Cover all columns having an assignment (columns 1 and 2).

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

|- style="background: white"

|× ||× || || ||

|-

|style="background:lightgrey"| 0*||style="background:lightgrey"|a2'a₂|| 0 ||a4'a₄

|style="background: white"|

|-

|style="background:lightgrey"|b1'b₁||style="background:lightgrey"| 0*||b3'b₃|| 0

|style="background: white"|

|-

|style="background:lightgrey"| 0 ||style="background:lightgrey"|c2'c₂||c3'c₃||c4'c₄

|style="background: white"|

|-

|style="background:lightgrey"| 0 ||style="background:lightgrey"|d2'd₂||d3'd₃||d4'd₄

|style="background: white"|

|}

* Find a non-covered zero and prime it. (If 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.

* Then, GOTO "Find a non-covered zero and prime it."
** Here, the second zero of Row 1 is uncovered. Because there is another zero starred on Row 1, we cover Row 1 and uncover Column 1.

** Then, the second zero of Row 2 is uncovered. We cover Row 2 and uncover Column 2.

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

Line 189 ⟶ 178:

|| ||× || || ||

|- style="background:lightgrey"

| 0*||a2'a₂|| 0'||a4'a₄

|style="background: white"|×

|-

|b1'b₁||style="background:lightgrey"| 0*||b3'b₃|| 0

|style="background: white"|

|-

|| 0 ||style="background:lightgrey"|c2'c₂||c3'c₃||c4'c₄

|style="background: white"|

|-

|| 0 ||style="background:lightgrey"|d2'd₂||d3'd₃||d4'd₄

|style="background: white"|

|}

Line 206 ⟶ 195:

|| || || || ||

|- style="background:lightgrey"

| 0*||a2'a₂|| 0'||a4'a₄

|style="background: white"|×

|- style="background:lightgrey"

|b1'b₁|| 0*||b3'b₃|| 0'

|style="background: white"|×

|-

|| 0 ||c2'c₂||c3'c₃||c4'c₄

|style="background: white"|

|-

|| 0 ||d2'd₂||d3'd₃||d4'd₄

|style="background: white"|

|}

* IfElse athe non-covered zero has no assigned zero on its row,. performWe make a path starting from the zero by performing the following steps :

**# StepSubstep 1: Find a starred zero on the corresponding column. If there is one, go to StepSubstep 2, else, stop.

**# StepSubstep 2: Find a primed zero on the corresponding row (there should always be one). Go to StepSubstep 1.

The zero on Row 3 is uncovered. We findadd onto the path the first zero of Row 1, then the second zero of Row 1, then we are done.

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

|- style="background: white"

|| || || || ||

|- style="background:lightgrey"

| <span style="color:red">0*</span> ||a2'a₂|| <span style="color:red">0'</span> ||a4'a₄

|style="background: white"|&times;

|- style="background:lightgrey"

|b1'b₁|| 0*||b3'b₃|| 0'

|style="background: white"|&times;

|-

|| <span style="color:red">0'</span> ||c2'c₂||c3'c₃||c4'c₄

|style="background: white"|

|-

|| 0 ||d2'd₂||d3'd₃||d4'd₄

|style="background: white"|

|}

*(Else branch continued) For all zeros encountered during the path, star primed zeros and unstar starred zeros, remove all covered lines and primed zeros.

**As the path begins and ends by a primed zero when swapping starred zeros, we have assigned one more zero.

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

|-

| 0 ||a2'a₂|| 0*||a4'a₄

|-

|b1'b₁|| 0*||b3'b₃|| 0

|-

|| 0*||c2'c₂||c3'c₃||c4'c₄

|-

|| 0 ||d2'd₂||d3'd₃||d4'd₄

|}

*(Else branch continued) Unprime all primed zeroes and uncover all lines.

* Repeat the previous steps

* Repeat the previous steps (continue looping until the above "skip to step 5" is reached).

** weWe cover columns 1, 2 and 3. The second zero on Row 2 is uncovered, so we cover Row 2 and uncover Column 2:

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

|- style="background: white"

||&times; || ||&times; || ||

|-

|style="background:lightgrey"| 0 ||a2'a₂||style="background:lightgrey"| 0*||a4'a₄

|style="background: white"|

|- style="background:lightgrey"

|b1'b₁|| 0*||b3'b₃|| 0'

|style="background: white"|&times;

|-

|style="background:lightgrey"| 0*||c2'c₂||style="background:lightgrey"|c3'c₃||c4'c₄

|style="background: white"|

|-

|style="background:lightgrey"| 0 ||d2'd₂||style="background:lightgrey"|d3'd₃||d4'd₄

|style="background: white"|

|}

Line 275 ⟶ 266:

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 45===

'''Find the lowest uncovered value. Subtract this from every unmarked element and add it to every element covered by two lines.'''

Line 281 ⟶ 272:

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.

Repeat steps 3–44–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}}