Hungarian Algorithm

Contenus

Also called algorithm of Kühn, the Hungarian algorithm, or Hungarian method solves assignment problems of the cost table type. Consider a number of machines and as many tasks. Each machine performs a task at a certain cost. The objective is to determine the machine on which each task will run, in parallel.

This problem being similar to a coupling problem in a graph, it meets König's criterion for nodal coverage of minimum weight. The objective is therefore to find one item per row and column in the table such that the sum of the costs is minimal. If we start from a maximization problem, it will be necessary to reverse the costs in order to fall back on a problem of minimization.

Let us take a simple example in order to show the process of the algorithm. Let 5 machines (row) and 5 tasks (column) give the following cost table:

17	15	9	5	12
16	16	10	5	10
12	15	14	11	5
4	8	14	17	13
13	9	8	12	17

Step 1 Hungarian algorithm: reduction of the initial table

We subtract from each line the smallest element of the line. The more we subtract from each column the smaller element of the column.

12	9	4	0	7
11	10	5	0	5
7	9	9	6	0
0	3	10	13	9
5	0	0	4	9

This standardization of machine and task costs makes it possible to have at least one zero per row and per column.

Hungarian Algorithm Step 2: Find a Workable Solution

We are looking for the line with the fewest non-crossed zeros. In the event of a tie, we will take the highest line.

We surround one of the zeros of this line (arbitrarily the one furthest to the left).
All zeros in the same row and column as the one selected are crossed out.
We start again until all the zeros are boxed or crossed out.

If we have framed a zero by row and by column, we have an optimal solution. Otherwise we go to step 3.

12	9	4	0	7
11	10	5	-0-	5
7	9	9	6	0
0	3	10	13	9
5	0	-0-	4	9

Step 3 Hungarian algorithm: creation of the pivots

The sub-table allows by subtraction to have a configuration making it possible to find an optimal solution. The construction of the pivots is done as follows:

We mark any line that does not contain any framed zero.
Any column with a crossed out zero is marked on a marked row.
We mark any row having a framed zero in a marked column.
Repeat 2 and 3 until no more changes.

A line is then drawn on any unmarked line and on any marked column. In our example, row 1 and 2 are marked, as well as column 4. Double-marked items are marked with a star.

12	9	4	-0-	7
11	10	5	-0-	5
-7-	-9-	-9-	-6-	-0-
-0-	-3-	-10-	-13-	-9-
-5-	-0-	-0-	-4-	-9-

Step 4 Hungarian algorithm: modification of the table

The cells not crossed by a line constitute a partial table.

We subtract from all the boxes of this table the smallest element thereof.
This element is added to all the boxes of the table crossed out in both directions (accompanied by a star).

Steps 2 to 4 are repeated until an optimal result is obtained. In our example, we get an optimal result after the first iteration.

8	5	0	0	3
7	6	1	0	1
7	9	9	10	0
0	3	10	17	9
5	0	0	8	9

The minimum allocation is calculated from the initial table: 9 + 5 + 5 + 4 + 9 = 32.

The following figure shows the changes in the bipartite graph with the Hungarian algorithm.