• Practice Mathematical Algorithm
  • Mathematical Algorithms
  • Pythagorean Triplet
  • Fibonacci Number
  • Euclidean Algorithm
  • LCM of Array
  • GCD of Array
  • Binomial Coefficient
  • Catalan Numbers
  • Sieve of Eratosthenes
  • Euler Totient Function
  • Modular Exponentiation
  • Modular Multiplicative Inverse
  • Stein's Algorithm
  • Juggler Sequence
  • Chinese Remainder Theorem
  • Quiz on Fibonacci Numbers

Hungarian Algorithm for Assignment Problem | Set 1 (Introduction)

hungarian1

  • For each row of the matrix, find the smallest element and subtract it from every element in its row.
  • Do the same (as step 1) for all columns.
  • Cover all zeros in the matrix using minimum number of horizontal and vertical lines.
  • Test for Optimality: If the minimum number of covering lines is n, an optimal assignment is possible and we are finished. Else if lines are lesser than n, we haven’t found the optimal assignment, and must proceed to step 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.
Try it before moving to see the solution

Explanation for above simple example:

  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.

Time complexity : O(n^3), where n is the number of workers and jobs. This is because the algorithm implements the Hungarian algorithm, which is known to have a time complexity of O(n^3).

Space complexity :   O(n^2), where n is the number of workers and jobs. This is because the algorithm uses a 2D cost matrix of size n x n to store the costs of assigning each worker to a job, and additional arrays of size n to store the labels, matches, and auxiliary information needed for the algorithm.

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. References: http://www.math.harvard.edu/archive/20_spring_05/handouts/assignment_overheads.pdf https://www.youtube.com/watch?v=dQDZNHwuuOY

Similar Reads

  • Mathematical

Improve your Coding Skills with Practice

 alt=

What kind of Experience do you want to share?

IMAGES

  1. Solution of Assignment Problems

    assignment problem solution for

  2. Assignment Problem Solution

    assignment problem solution for

  3. How to Solve the Assignment Problem in Excel

    assignment problem solution for

  4. How to Write a Problem Solution Essay

    assignment problem solution for

  5. Assignment Problem

    assignment problem solution for

  6. Problem/Solution (Proposal) Assignment

    assignment problem solution for

VIDEO

  1. September 16, 2021 Assignment problem| Part 2

  2. Assignment Problem ( Brute force method) Design and Analysis of Algorithm

  3. شرح Assignment Problem

  4. Assignment problem

  5. Assignment Problem

  6. GATE 2022 MATHEMATICS (MA) SOLUTION || ASSIGNMENT PROBLEM SOLUTION GATE 2022 MATHEMATICS (MA)