Why does hungarian algorithm work

We slightly modified the example by making the cost matrix non-square. To avoid duplicating the solution on Brilliant, instead of solving it manually, we will use the existing SciPy linear sum assignment optimizer to solve, and verified using a brute force solver.

Here is the way to understand this. The cost of each assignment consists of two parts, the cost from one of the entries in the selected row and the cost from the entries in the other rows. This means a number is added to or subtracted from the selected row, the optimal assignment is still the optimal.

Similarly, we could understand it for adding or subtracting a number from a selected column. So the minimum cost assignment problem could be formulated as a linear programming problem mathematically as follows. Note that for maximum cost assignment problem, it could be formulated as the following minimization problem as well.

Note that the behavior of subtracting values from rows and columns in the Hungarian algorithm is encoded in this step. This partially explains why Hungarian algorithm works. However, it does not explain why the magic values exists and how the magic values are determined. The rationale behind this is related to the duality of a linear programming optimization problem. More details could be found from Katta G.

Frankly, I really need to find some time to go through this chapter. I rarely applaud for deep learning algorithms. Conventional algorithms such as the Hungarian matching algorithm are truly amazing. What if we the number covering lines is less than n. Step 4: Since we only need 2 lines to cover all zeroes, we have NOT found the optimal assignment. Step 5: We subtract the smallest uncovered entry from all uncovered rows.

Smallest entry is Here we cover again using lines. Since we need 3 lines to cover, we found the optimal solution. Please write comments if you find anything incorrect, or you want to share more information about the topic discussed above. Skip to content.

Change Language. Related Articles. Table of Contents. Save Article. Improve Article. Like Article. If n lines are required, an optimal assignment exists among the zeros.

The algorithm stops. Find the smallest element call it k that is not covered by a line in Step 3. Subtract k from all uncovered elements, and add k to all elements that are covered twice. The Hungarian algorithm explained based on an example.

The Hungarian algorithm explained based on a self chosen or on a random cost matrix.