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!

Take Quiz
 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 Save

Want to watch this again later?

Log in or sign up to add this lesson to a Custom Course.

Log in or Sign up

Timeline
Autoplay
Autoplay
Speed

Recommended Lessons and Courses for You

Lesson Transcript
Instructor: Laura Pennington

Laura has taught collegiate mathematics and holds a master's degree in pure mathematics.

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.


Hung1


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).


Hung2


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.


Hung3


Now we subtract column minima. We go column by column and subtract the smallest entry in each column from that column's entries.


Hung4


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.


Hung5


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.


Hung6


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

Register to view this lesson

Are you a student or a teacher?

Unlock Your Education

See for yourself why 30 million people use Study.com

Become a Study.com member and start learning now.
Become a Member  Back
What teachers are saying about Study.com
Try it risk-free for 30 days

Earning College Credit

Did you know… We have over 200 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.

To learn more, visit our Earning Credit Page

Transferring credit to the school of your choice

Not sure what college you want to attend yet? Study.com has thousands of articles about every imaginable degree, area of study and career path that can help you find the school that's right for you.

Create an account to start this course today
Try it risk-free for 30 days!
Create an account
Support