Hungarian Algorithm for Assignment Problem | Set 1 (Introduction) - G... https://www.geeksforgeeks.org/hungarian-algorithm-assignment-problem...
Data Structures Algorithms Interview Preparation Topic-wise Practice C++ Java Python
Hungarian Algorithm for Assignment
Problem | Set 1 (Introduction)
Difficulty Level : Hard ● Last Updated : 04 Mar, 2020
Let there be n agents and n tasks. Any agent can be assigned to perform
any task, incurring some cost that may vary depending on the agent-task
assignment. It is required to perform all tasks by assigning exactly one
agent to each task and exactly one task to each agent in such a way that
the total cost of the assignment is minimized.
Example: You work as a manager for a chip manufacturer, and you
currently have 3 people on the road meeting clients. Your salespeople are
in Jaipur, Pune and Bangalore, and you want them to fly to three other
cities: Delhi, Mumbai and Kerala. The table below shows the cost of
airline tickets in INR between the cities:
The question: where would you send each of your salespeople in order to
minimize fair?
Possible
We use assignment:
cookies to ensure Cost
you have the best = 11000
browsing INRon our website. By using our site, you acknowledge that
experience
you have read and understood our Cookie Policy & Privacy Policy
Got It !
▲
1 of 10 11-03-2022, 01:19 am
Hungarian Algorithm for Assignment Problem | Set 1 (Introduction) - G... https://www.geeksforgeeks.org/hungarian-algorithm-assignment-problem...
Other Possible assignment: Cost = 9500 INR and this is the best of the 3!
possible assignments.
Brute force solution is to consider every possible assignment implies a
complexity of Ω(n!).
The Hungarian algorithm, aka Munkres assignment algorithm, utilizes
the following theorem for polynomial runtime complexity (worst case
O(n3)) and guaranteed optimality:
If a number is added to or subtracted from all of the entries of any one
row or column of a cost matrix, then an optimal assignment for the
resulting cost matrix is also an optimal assignment for the original cost
matrix.
We reduce our original weight matrix to contain zeros, by using the above
theorem. We try to assign tasks to agents such that each agent is doing
only one task and the penalty incurred in each case is zero.
Core of the algorithm (assuming square matrix):
1. For each row of the matrix, find the smallest element and subtract it
from every element in its row.
2. Do the same (as step 1) for all columns.
3. Cover all zeros in the matrix using minimum number of horizontal and
vertical lines.
4. Test for Optimality: If the minimum number of covering lines is n, an
We use cookies to ensure you have the best browsing experience on our website. By using our site, you acknowledge that
optimal assignment
you have read is
andpossible and
understood our wePolicy
Cookie are &finished. Else if lines are
Privacy Policy
lesser than n, we haven’t found
Gotthe
It ! optimal assignment, and must
▲
2 of 10 11-03-2022, 01:19 am
Hungarian Algorithm for Assignment Problem | Set 1 (Introduction) - G... https://www.geeksforgeeks.org/hungarian-algorithm-assignment-problem...
proceed to step 5.
5. Determine the smallest entry not covered by any line. Subtract this
entry from each uncovered row, and then add it to each covered
column. Return to step 3.
Explanation for above simple example:
Below is the cost matrix of example given in above diagrams.
2500 4000 3500
4000 6000 3500
2000 4000 2500
Step 1: Subtract minimum of every row.
2500, 3500 and 2000 are subtracted from rows 1, 2 and
3 respectively.
0 1500 1000
500 2500 0
0 2000 500
Step 2: Subtract minimum of every column.
0, 1500 and 0 are subtracted from columns 1, 2 and 3
respectively.
0 0 1000
500 1000 0
0 500 500
Step 3: Cover all zeroes with minimum number of
horizontal and vertical lines.
We use cookies to ensure you have the best browsing experience on our website. By using our site, you acknowledge that
you have read and understood our Cookie Policy & Privacy Policy
Got It !
▲
3 of 10 11-03-2022, 01:19 am
Hungarian Algorithm for Assignment Problem | Set 1 (Introduction) - G... https://www.geeksforgeeks.org/hungarian-algorithm-assignment-problem...
Step 4: Since we need 3 lines to cover all zeroes,
we have found the optimal assignment.
2500 4000 3500
4000 6000 3500
2000 4000 2500
So the optimal cost is 4000 + 3500 + 2000 = 9500
An example that doesn’t lead to optimal value in first attempt:
In the above example, the first check for optimality did give us solution.
What if we the number covering lines is less than n.
cost matrix:
1500 4000 4500
2000 6000 3500
2000 4000 2500
Step 1: Subtract minimum of every row.
1500, 2000 and 2000 are subtracted from rows 1, 2 and
3 respectively.
0 2500 3000
0 4000 1500
0 2000 500
Step 2: Subtract minimum of every column.
0, 2000 and 500 are subtracted from columns 1, 2 and 3
respectively.
0 500 2500
0 2000 1000
We use cookies to ensure you have the best browsing experience on our website. By using our site, you acknowledge that
0 0 you have 0 read and understood our Cookie Policy & Privacy Policy
Got It !
▲
4 of 10 11-03-2022, 01:19 am
Hungarian Algorithm for Assignment Problem | Set 1 (Introduction) - G... https://www.geeksforgeeks.org/hungarian-algorithm-assignment-problem...
Step 3: Cover all zeroes with minimum number of
horizontal and vertical lines.
Step 4: Since we only need 2 lines to cover all zeroes,
we have NOT found the optimal assignment.
Step 5: We subtract the smallest uncovered entry
from all uncovered rows. Smallest entry is 500.
-500 0 2000
-500 1500 500
0 0 0
Then we add the smallest entry to all covered columns, we get
0 0 2000
0 1500 500
500 0 0
Now we return to Step 3:. Here we cover again using
lines. and go to Step 4:. Since we need 3 lines to
cover, we found the optimal solution.
1500 4000 4500
2000 6000 3500
2000 4000 2500
So the optimal cost is 4000 + 2000 + 2500 = 8500
In the next post, we will be discussing implementation of the above
algorithm. The implementation requires more steps as we need to find
minimum number of lines to cover all 0’s using a program.
We use cookies to ensure you have the best browsing experience on our website. By using our site, you acknowledge that
you have read and understood our Cookie Policy & Privacy Policy
References: Got It !
▲
5 of 10 11-03-2022, 01:19 am
Hungarian Algorithm for Assignment Problem | Set 1 (Introduction) - G... https://www.geeksforgeeks.org/hungarian-algorithm-assignment-problem...
http://www.math.harvard.edu/archive/20_spring_05/handouts
/assignment_overheads.pdf
https://www.youtube.com/watch?v=dQDZNHwuuOY
This article is contributed by Yash Varyani. Please write comments if you
find anything incorrect, or you want to share more information about the
topic discussed above.
Like 18
Previous Next
Transportation Problem Set 8 Channel Assignment Problem
| Transshipment Model-1
ADVERTISEMENT BY ADRECOVER
We use cookies to ensure you have the best browsing experience on our website. By using our site, you acknowledge that
you have read and understood our Cookie Policy & Privacy Policy
Got It !
▲
6 of 10 11-03-2022, 01:19 am
Hungarian Algorithm for Assignment Problem | Set 1 (Introduction) - G... https://www.geeksforgeeks.org/hungarian-algorithm-assignment-problem...
R ECO M M E N D E D A RT I C L E S Page : 1 2 3
01 Hungarian Algorithm for
Assignment Problem | Set 2
05 K Centers Problem | Set 1
(Greedy Approximate
(Implementation) Algorithm)
20, Jul 21 26, Mar 15
02 Channel Assignment Problem
23, Jun 14 06 Transportation Problem | Set 1
(Introduction)
25, Nov 19
03 Vertex Cover Problem | Set 1
(Introduction and Approximate
Algorithm)
07 Push Relabel Algorithm | Set 1
(Introduction and Illustration)
17, Nov 14 04, Apr 16
04 Transportation Problem | Set 7 (
Degeneracy in Transportation
08 Karger's algorithm for Minimum
Cut | Set 1 (Introduction and
Problem ) Implementation)
03, Dec 19 21, May 15
Article Contributed By :
GeeksforGeeks
We use cookies to ensure you have the best browsing experience on our website. By using our site, you acknowledge that
you have read and understood our Cookie Policy & Privacy Policy
Vote for di�culty
Current di�culty : Hard Got It !
▲
7 of 10 11-03-2022, 01:19 am
Hungarian Algorithm for Assignment Problem | Set 1 (Introduction) - G... https://www.geeksforgeeks.org/hungarian-algorithm-assignment-problem...
Easy Normal Medium Hard Expert
Improved By : Rohit_Goyal
Article Tags : Google, Graph, Mathematical
Practice Tags : Google, Mathematical, Graph
Improve Article Report Issue
Writing code in comment? Please use ide.geeksforgeeks.org, generate link and share the link here.
ADVERTISEMENT BY ADRECOVER
Load Comments
We use cookies to ensure you have the best browsing experience on our website. By using our site, you acknowledge that
you have read and understood our Cookie Policy & Privacy Policy
Got It !
▲
8 of 10 11-03-2022, 01:19 am
Hungarian Algorithm for Assignment Problem | Set 1 (Introduction) - G... https://www.geeksforgeeks.org/hungarian-algorithm-assignment-problem...
5th Floor, A-118,
Sector-136, Noida, Uttar Pradesh - 201305
feedback@geeksforgeeks.org
Company Learn
About Us Algorithms
Careers Data Structures
In Media SDE Cheat Sheet
Contact Us Machine learning
Privacy Policy CS Subjects
Copyright Policy Video Tutorials
News Languages
Top News Python
Technology Java
Work & Career CPP
Business Golang
Finance C#
Lifestyle SQL
Web Development Contribute
Web Tutorials Write an Article
Django Tutorial Improve an Article
HTML Pick Topics to Write
CSS Write Interview Experience
We use cookies to ensure you have the best browsing experience on our website. By using our site, you acknowledge that
JavaScript Internships
you have read and understood our Cookie Policy & Privacy Policy
Bootstrap Got It ! Video Internship
▲
9 of 10 11-03-2022, 01:19 am
Hungarian Algorithm for Assignment Problem | Set 1 (Introduction) - G... https://www.geeksforgeeks.org/hungarian-algorithm-assignment-problem...
@geeksforgeeks , Some rights reserved
We use cookies to ensure you have the best browsing experience on our website. By using our site, you acknowledge that
you have read and understood our Cookie Policy & Privacy Policy
Got It !
▲
10 of 10 11-03-2022, 01:19 am
