The Hungarian Method

History 

Harold Kuhn

The Hungarian method is a combinatorial optimization  algorithm that solves the assignment problem in polynomial time and which anticipated later primal-dual methods. It was developed and published in 1955 by Harold Kuhn, who gave the name "Hungarian method" because the algorithm was largely based on the earlier works of two Hungarian mathematicians: Dénes Kőnig and Jenő Egerváry. James Munkres reviewed the algorithm in 1957 and observed that it is (strongly) polynomial. Since then the algorithm has been known also as the Kuhn–Munkres algorithm or Munkres assignment algorithm. The time complexity of the original algorithm was, however Edmonds and Karp, and independently Tomizawa noticed that it can be modified to achieve an   running time. Ford and Fulkerson extended the method to general transportation problems. In 2006, it was discovered that Carl Gustav Jacobi had solved the assignment problem in the 19^th  century, and the solution had been published posthumously in 1890 in Latin.

FLOW CHART OF THE STEPS IN THE HUNGARIAN METHOD

Solved example

In order to find the proper assignment, we apply the Hungarian method as follows:

  1. Find the minimum entry in each row and subtract it from each row 

  (table 1)

  2. Find the minimum entry in each column and subtract it from each column 

  (table 2)

   ª  Resulting matrix is non negative

   3.     Zero assignment

    From the last table we see that all the zeros are either assigned or crossed out, but the total number     of assignment is 4, less than 5 (number of jobs to be assigned to machines).

    (table 3)

   Therefore we have to do the following.

    4.     Using lines that go all the way across or all the way up-and-down, cross out all zeros in the new         cost matrix

        (table 4)

ª  Find a way to do this with a minimum number of lines (≤n)

    5.     Here, the smallest element among the uncovered elements is 2.

     (i)                 Subtract 2 from all those elements which are not covered.

    (ii)                Add 2 to those entries which are at the junction of two lines

(table 5)

     6.     Finally we get table 6.

Thus, we have got five assignments as required by the problem. The assignment is as follows:

job1 → machine1        

job2 → machine4    

job3 → machine5       

job4 → machine3                                         

job5 → machine2

 This assignment holds for table given in step IV but from theorem 1 it also holds for the original cost matrix. Thus from the cost matrix the minimum cost = 6+1+11+12+5=Rs.35.

Note: If we are given a maximization problem then convert it into minimization problem, simply, multiplying by -1 to each entry in the effectiveness matrix and then solve it in the usual manner.