Also called Kühn algorithm, the Hungarian algorithm, or Hungarian method solves cost allocation table. Consider a number of machines and as many tasks. Each machine performs a task at a certain cost. The goal is to determine the machine on which each task will run, in parallel.
Let’s take a simple example to show the process of the algorithm. There are 5 machines (line) and 5 tasks (column) giving 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: Reduction of the initial table
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 costs and tasks makes it possible to have at least one zero per line and per column.
Step 2: Find a feasible solution
We are looking for the line with the fewest zeros. In case of equality we will take the highest line.
 We frame one of the zeros of this line (arbitrarily the one on the left).
 We mark all zeros on the same row and column as the one selected.
 We start again until all the zeros are framed or crossed out.
If we have a zero per line and 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: Creating pivots
The subtable allows by retrench to have a configuration to find an optimal solution. The construction of the pivots is as follows:
 Mark all rows having no assignments.
 Mark all (unmarked) columns having zeros in newly marked row(s).
 Mark all rows having assignments in newly marked columns.
 Repeat for all nonassigned rows.
A line is then drawn on any unmarked line and any marked column. In our example, the lines 1 and 2 are marked, as well as the column 4. The elements twice marked are accompanied by 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: Edit the table
Non crossings elements with a line are a partial table.
 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.
 Repeat steps 2–4 until an assignment is possible
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.