Laura received her Master's degree in Pure Mathematics from Michigan State University. She has 15 years of experience teaching collegiate mathematics at various institutions.
The Hungarian Algorithm is used in assignment problems when we want to minimize cost. This lesson will go over the steps of this algorithm and we will also see this algorithm in action by applying it to a real-world example.
The Hungarian Algorithm
Suppose you own a business, and you have four employees to choose from to complete three jobs you need done. The following table displays the cost of each job for each employee.
This table is also called a matrix, which is an array of elements in rows and columns.
You want to assign the employees to jobs in such a way that the overall cost is minimized. This is an example of an assignment problem that we can use the Hungarian Algorithm to solve. The Hungarian Algorithm is used to find the minimum cost when assigning people to activities based on cost, and each activity must be assigned to a different person.
Hungarian Algorithm Steps
To use the Hungarian Algorithm, we first arrange the activities and people in a matrix with rows being people, columns being activity, and entries being the costs. Once we've done this, we make sure the number of rows equals the number of columns by adding dummy columns or rows with entries equal to the largest cost in the entire matrix.
After we've got our square matrix, the steps of the algorithm are as follows:
Subtract row minima - Subtract the smallest entry in each row from each entry in that row.
Subtract column minima - Subtract the smallest entry in each column from each entry in that column.
Cover all zeros with the minimum number of lines - Using the smallest number of lines possible, draw lines over rows and columns in order to cover all zeros in the matrix. If the number of lines is equal to the number of rows in your square matrix, stop here. Otherwise, go to step 4.
Create additional zeros - Find the smallest element - call it c - that isn't covered by a line. Subtract c from all uncovered elements in the matrix and add it to any element that's covered twice. Go back to step 3.
Once you can stop the algorithm, choose a set of zeros such that each row and column only has one zero selected. Now take out any dummy rows or columns that you added. The zeros in the final matrix correspond to the ideal assignment in the original matrix. Let's put this into action to make it more understandable!
Hungarian Algorithm Application
First, we want to turn our matrix into a square matrix by adding a dummy column with entries equal to 518 (the highest entry in the matrix).
Now we have a 4 by 4 square matrix, so we can start the algorithm.
The first step is to subtract row minima, so we go row by row and subtract the smallest entry in each row from that row's entries.
Now we subtract column minima. We go column by column and subtract the smallest entry in each column from that column's entries.
On to the third step! We want to cover all of the zeros in the matrix using the minimum number of lines. Notice we can do this using three lines.
Because 3 obviously doesn't equal 4, as in the number of rows in the square matrix, we move on to step 4. In this step, we identify the smallest uncovered element in the matrix as 10, and we subtract it from the uncovered elements and add it to any element that's covered by two lines.
Back to step 3! Again, we determine the number of lines needed to cover all the zeros.
This time we need a minimum of four lines in order to cover all the zeros, and four is equal to the number of rows or columns of our matrix, so we can stop.
Once we are able to stop like this, we choose a set of zeros in the matrix so that each row and column only has one zero selected. Then we take out the dummy column.
The zeros in the resulting matrix correspond to the entries in the original matrix that will result in the ideal assignment to minimize your cost.
The minimum cost is 421 + 407 + 411 = $1,239, and it happens when you assign job 1 to employee 2, job 2 to employee 3, and job 3 to employee 4. Looks like employee 1 is out of luck, but at least you know how to assign the jobs in order to minimize your cost.
The Hungarian Algorithm is used to find the minimum cost in assignment problems that involve assigning people to activities. To use this algorithm, we start by organizing our data into a matrix with people as the rows and activities as the columns. If it's not a square matrix, we make it one by adding dummy rows/columns with entries equal to the highest cost in the matrix. Then the steps of the Hungarian Algorithm are as follows:
Subtract row minima.
Subtract column minima.
Cover all zeros with the minimum number of lines. If the number of lines is equal to the number of rows or columns in your matrix, stop here. Otherwise, go to step 4.
Create additional zeros by finding the smallest element - call it c - that isn't covered by a line. Subtract c from all uncovered elements in the matrix and add it to any element that's covered by two lines. Go back to step 3.
Once you're able to stop the algorithm, you choose a set of zeros so that there is just one selected in each row and column, then take out the dummy rows and columns. The selected zeros correspond to the ideal assignment in the original matrix. Once you get used to the process, the Hungarian Algorithm is a cinch, so keep practicing.
Did you know… We have over 220 college
courses that prepare you to earn
credit by exam that is accepted by over 1,500 colleges and universities. You can test out of the
first two years of college and save thousands off your degree. Anyone can earn
credit-by-exam regardless of age or education level.