## Hungarian algorithm

Also called algorithm de Kühn, l’algorithme hongrois, ou méthode hongroise résout des problèmes d’affectation de type table de coûts. Considérons un certain nombre de machines et autant de tâches. Chaque machine exécute une tâche à un certain coût. L’objectif est de déterminer la machine sur laquelle s’exécutera chaque tâche, en parallèle.

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.