Contenus

Toggle## Hungarian algorithm

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.

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

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.