# Using the Hungarian Algorithm to Solve Assignment Problems

An error occurred trying to load this video.

Try refreshing the page, or contact customer support.

Coming up next:

### You're on a roll. Keep up the good work!

Replay
Your next lesson will play in 10 seconds
• 0:04 The Hungarian Algorithm
• 0:38 Hungarian Algorithm Steps
• 2:02 Hungarian Algorithm…
• 3:45 Lesson Summary
Save Save

Want to watch this again later?

Timeline
Autoplay
Autoplay
Speed Speed

#### Recommended Lessons and Courses for You

Lesson Transcript
Instructor: Laura Pennington

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:

1. Subtract row minima - Subtract the smallest entry in each row from each entry in that row.
2. Subtract column minima - Subtract the smallest entry in each column from each entry in that column.
3. 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.
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.

To unlock this lesson you must be a Study.com Member.

### Register to view this lesson

Are you a student or a teacher?

#### See for yourself why 30 million people use Study.com

##### Become a Study.com member and start learning now.
Back
What teachers are saying about Study.com

### Earning College Credit

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.