 ### Lei Mao

Machine Learning, Artificial Intelligence, Computer Science.

# Hungarian Matching Algorithm

### Introduction

The Hungarian matching algorithm is a combinatorial optimization algorithm that solves the assignment linear-programming problem in polynomial time. The assignment problem is an interesting problem and the Hungarian algorithm is difficult to understand.

In this blog post, I would like to talk about what assignment is and give some intuitions behind the Hungarian algorithm.

### Minimum Cost Assignment Problem

#### Problem Definition

In the matrix formulation, we are given a nonnegative $n \times n$ cost matrix, where the element in the $i$-th row and $j$-th column represents the cost of assigning the $j$-th job to the $i$-th worker. We have to find an assignment of the jobs to the workers, such that each job is assigned to one worker, each worker is assigned one job, and the total cost of assignment is minimum.

Finding a brute-force solution for this problem takes $O(n!)$ because the number of valid assignments is $n!$. We really need a better algorithm, which preferably takes polynomial time, to solve this problem.

#### Maximum Cost Assignment VS Minimum Cost Assignment

Solving a maximum cost assignment problem could be converted to solving a minimum cost assignment problem, and vice versa. Suppose the cost matrix is $c$, solving the maximum cost assignment problem for cost matrix $c$ is equivalent to solving the minimum cost assignment problem for cost matrix $-c$. So we will only discuss the minimum cost assignment problem in this article.

#### Non-Square Cost Matrix

In practice, it is common to have a cost matrix which is not square. But we could make the cost matrix square, fill the empty entries with $0$, and apply the Hungarian algorithm to solve the optimal cost assignment problem.

### Hungarian Matching Algorithm

#### Algorithm

Brilliant has a very good summary on the Hungarian algorithm for adjacency cost matrix. Let’s walk through it.

1. Subtract the smallest entry in each row from all the other entries in the row. This will make the smallest entry in the row now equal to 0.
2. Subtract the smallest entry in each column from all the other entries in the column. This will make the smallest entry in the column now equal to 0.
3. Draw lines through the row and columns that have the 0 entries such that the fewest lines possible are drawn.
4. If there are nn lines drawn, an optimal assignment of zeros is possible and the algorithm is finished. If the number of lines is less than nn, then the optimal number of zeroes is not yet reached. Go to the next step.
5. Find the smallest entry not covered by any line. Subtract this entry from each row that isn’t crossed out, and then add it to each column that is crossed out. Then, go back to Step 3.

Note that we could not tell the algorithm time complexity from the description above. The time complexity is actually $O(n^3)$ where $n$ is the side length of the square cost adjacency matrix.

#### Example

The Brilliant Hungarian algorithm for adjacency cost matrix also comes with a good example. We slightly modified the example by making the cost matrix non-square.

Company Cost for Musician Cost for Chef Cost for Cleaners
Company A 108 125 150
Company B 150 135 175

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.

# hungarian.py
from typing import List, Tuple
import itertools
import numpy as np
from scipy.optimize import linear_sum_assignment

def linear_sum_assignment_brute_force(
cost_matrix: np.ndarray,
maximize: bool = False) -> Tuple[List[int], List[int]]:

h = cost_matrix.shape
w = cost_matrix.shape

if maximize is True:
cost_matrix = -cost_matrix

minimum_cost = float("inf")

if h >= w:
for i_idices in itertools.permutations(list(range(h)), min(h, w)):
row_ind = i_idices
col_ind = list(range(w))
cost = cost_matrix[row_ind, col_ind].sum()
if cost < minimum_cost:
minimum_cost = cost
optimal_row_ind = row_ind
optimal_col_ind = col_ind
if h < w:
for j_idices in itertools.permutations(list(range(w)), min(h, w)):
row_ind = list(range(h))
col_ind = j_idices
cost = cost_matrix[row_ind, col_ind].sum()
if cost < minimum_cost:
minimum_cost = cost
optimal_row_ind = row_ind
optimal_col_ind = col_ind

return optimal_row_ind, optimal_col_ind

if __name__ == "__main__":

cost_matrix = np.array([[108, 125, 150], [150, 135, 175]])

row_ind, col_ind = linear_sum_assignment_brute_force(
cost_matrix=cost_matrix, maximize=False)

minimum_cost = cost_matrix[row_ind, col_ind].sum()

print(
f"The optimal assignment from brute force algorithm is: {list(zip(row_ind, col_ind))}."
)
print(f"The minimum cost from brute force algorithm is: {minimum_cost}.")

row_ind, col_ind = linear_sum_assignment(cost_matrix=cost_matrix,
maximize=False)

minimum_cost = cost_matrix[row_ind, col_ind].sum()

print(
f"The optimal assignment from Hungarian algorithm is: {list(zip(row_ind, col_ind))}."
)
print(f"The minimum cost from Hungarian algorithm is: {minimum_cost}.")


### Final Remarks

I rarely applaud for deep learning algorithms. Conventional algorithms such as the Hungarian matching algorithm are truly amazing.