The Hungarian Algorithm for Assignment Problem Explained
What is the Hungarian Algorithm?
The simplest way to explain what the Hungarian algorithm is that it is an optimization algorithm that can be applied for an assignment problem. Its main objective is to minimize the overall costs incurred in a certain assignment scenario. The assignment problem is itself one of the most fundamental problems in mathematics that has a huge number of applications in the practical field.
Generally speaking, the Hungarian Algorithm for Assignment Problem has the following structure. The problem sets out a multitude of agents and tasks and sets up a situation where each of these agents can perform any of the stated tasks. However, each agent can only perform a maximum of one task each. The idea is to arrange the tasks in such a way that the total cost incurred is the least possible.
A Brief History of the Hungarian Algorithm
The person responsible for developing and publishing the algorithm is Harold Kuhn, way back in 1955. He was the one who gave the algorithm its name. The reasoning behind it is that most of Kuhn’s work is done based on the works of 2 mathematicians from Hungary. There was further work done on the same algorithm in the future as well.
It was found out that the Hungarian Algorithm for Assignment Problem initially had a time complexity of O (n^{4}). However, later on, there were modifications made to it which allowed the algorithm to reduce its time complexity to O (n^{3}). It was also extended to be compatible with transportation problems in general. Overall, the efficiency for solving assignment problems using this algorithm has increased significantly since it was first invented.
The Basic Setup of the Problem
So how does a basic assignment problem look like? And what are the steps required to solve this problem using the Hungarian Algorithm? The basic procedures that one needs to follow when going about said problem would look something like this.
The Question:
There are 3 workers John, Liam and Harry who happen to be places A, B and C respectively. They need to be sent to places X, Y and Z such that there is one person in each of X, Y and Z. The costs required for travelling from each of these places to the other is given in the table below. You need to find the combination that gives the least possible expenditure for the trip.
X | Y | Z | |
A | 2000 | 4000 | 3000 |
B | 4000 | 6000 | 2000 |
C | 2000 | 4000 | 1000 |
Solution (Primitive):
Since the total number of data is not high in the given problem, it is pretty intuitive as to what the final answer should be. You can use hit and trial method (which is basically brute forcing) and test all of the different combinations for each one. Once you have the total set, selecting the lowest costed combination is the optimal solution that you are looking for.
First Possibility
For instance, you could make the selections as follows:
- A to X (2000)
- B to Y (6000)
- C to Z (1000)
The total expenditure that you would have to pay is 9000 units.
Second Possibility
Another selection you could make is:
- A to Y (4000)
- B to Z (2000)
- C to X (2000)
The total expenditure here is 8000 units. So this is a better solution compared to the previous one. By the brute force technique, you would have to continue in this same fashion taking all possibilities into account and eventually finding the lowest one.
However, this method is obviously not the most efficient one. It is applicable for problems that have a lower number of data items involved which makes calculating all of the permutations much simpler. For larger data sets, this process is inconvenient and wasteful of resources and time. This is where the Hungarian Algorithm for Assignment Problem steps into the frame and makes things a lot easier.
Using the Hungarian Algorithm
There is a basic theorem that is in function when the Hungarian Algorithm is applied for solving an assignment problem. The worst case time complexity when using this algorithm is of the order O (n^{3}). It makes use of a certain property of matrices that allows it to find a solution that is fully optimized. In fact, optimality is something of a guarantee.
If you add or subtract an arbitrary number from any row or a column of a given cost matrix, the assignment which is the most optimal for the resultant cost matrix is the same as that of the original one. As a direct result of this property, the main weight matrix is reduced to contain only zeroes. We try to make it so that the cost incurred in each of the cases is 0. Only then can the Hungarian Algorithm for Assignment Problem proceed into the next stage.
The Idea of the Algorithm
The algorithm itself proceeds as follows:
- Find the smallest element in each row of the matrix. Subtract this element from all of the other elements in the row.
- Repeat the same procedure for columns.
- The next step is to cover all of the zeroes produced in the matrix using lines, both horizontal and vertical. The number of lines should be minimal.
- We then count the number of lines that are needed to be drawn. If it equals the order of the matrix, then an optimal solution is possible. If the number of lines is lesser in comparison, the optimal solution may not have been found yet and the next step must be executed.
- Next, find the smallest element in the matrix that has not been covered by any of the lines. You will have to subtract this element from each of the uncovered rows remaining and then add it to each of the covered columns.
General Problem Statement
Now that we know about the Hungarian Algorithm for Assignment Problem in its true form, it is time to generalize the overall problem. The assignment problem goes something like this. Assume that you have a total of n resources which you need to assign to n tasks in a one to one mapping scheme. Keep in mind that all of the resources need to be assigned to all of the tasks i.e. it must be a complete mapping.
Also assume that you know all of the costs required to assign a resource to a given task. Given all of the information stated above, what you need to find out is the most optimal way of assigning these resources to tasks, such that the total costs incurred is the minimum. As such, it is basically a minimization problem at its very core. This idea should help you understand the logic behind some of the steps mentioned above.
What you need in order to find the solution to such a problem is the mathematical model for the general statement of a given problem. In this case, we present this model in the form of a square n x n matrix as shown below.
Assume that C (i, j) is the cost incurred in assigning the ith number resource to the jth number task. The cost matrix is defined to be of the order of n x n and is shown above. The sum of all the entries in the matrix is considered to be the total cost of the matrix. Also, it is intuitive that the lowest cost possible in the matrix is known as the optimal assignment for the given matrix. Thus, the Hungarian Algorithm for Assignment Problem is formalized into a standard form.
Overall
Generally speaking, the Hungarian algorithm is one of the most efficient methods of solving the minimization problem in assignment operations. There are several others that have been meted out and are equally used, keeping in mind the kind of problems we are facing. Some of the other options that you have at your disposal include the simplex algorithm and the auction algorithm alongside its different variants.
After all, the assignment problem at its very core is simply a variation of the transportation problem. The transportation problem on the other hand is a variation of the minimum cost flow problem which also happens to be a more complicated derivative of the linear problem. And as we all know, the linear problem can be solved using the simplex method.
As such, by using the relations stated above, it is logical to say that it is possible to solve an assignment problem using simplex method alone. Each algorithm specializes in a certain aspect of calculation which is why it is important to understand exactly what that is.
The Hungarian Algorithm for Assignment Problem is no different. You should have a clear understanding about why this algorithm is as efficient as people call it to be and where you should apply it. All of the theory mentioned above should help you get an idea regarding what that is or what that is supposed to be like.