3 Hungarian Algorithm
This chapter covers
- Solving the assignment problem with the Hungarian algorithm
- Constructing the cost matrix and executing the row-column reductions
- Analyzing the algorithmic optimization from O(n!) to O(n3)
The Hungarian algorithm, also called the Kuhns-Munkres algorithm, is named after Harold W. Kuhn and James Munkres. This is a classic assignment problem to find an optimal one-to-one matching between two sets. This combinatorial optimization algorithm’s purpose is to minimize the total cost or maximize profit by assigning n workers to n tasks.
If the number of workers and the number of tasks are equal, then it's a balanced assignment problem. After looking at a string matching algorithm in the previous chapter, in this chapter, we will see a balanced cost minimization assignment problem. The time complexity of the algorithm is O(n!), but it is further optimized to O(n3) called polynomial time.
We use an n x n matrix where n is the size of the matrix with rows as workers and columns as tasks, and the matrix[i][j] has the cost we need to minimize to allocate the workers respective tasks.
3.1 Allocation problem in a nutshell
We are given a set of workers and tasks. Each worker can perform any task but incurs a fixed cost to complete the task based on distance, resources, or time. Our objective is to create a 1-1 mapping that optimizes the global cost.