How to Use the Hungarian Algorithm

The Hungarian algorithm allows a "minimum matching" to be found. This can be used in instances where there are multiple quotes for a group of activities and each activity must be done by a different person, to find the minimum cost to complete all of the activities.

Steps

  1. 1
    Image titled Matrix1_393
    Arrange your information in a matrix with the "people" on the left and the "activity" along the top, with the "cost" for each pair in the middle.
  2. 2
    Image titled Matrix2_102
    Ensure that the matrix is square by the addition of dummy rows/columns if necessary.
    Conventionally, each element in the dummy row/column is the same as the largest number in the matrix.
  3. 3
    Image titled Matrix3_952
    Reduce the rows by subtracting the minimum value of each row from that row.
  4. 4
    Image titled Matrix4_691
    If there are columns without a zero, reduce the columns by subtracting the minimum value of each column from that column.
  5. 5
    Image titled Matrix5_750
    Cover the zero elements with the minimum number of lines it is possible to cover them with.
    (If the number of lines is equal to the number of rows then go to step 9)
  6. 6
    Image titled Matrix6_172
    Add the minimum uncovered element to every covered element.
    If an element is covered twice, add the minimum element to it twice.
  7. 7
    Image titled Matrix7_164
    Subtract the minimum element from every element in the matrix.
  8. 8
    This example had to be reduced once more
    Cover the zero elements again.
    If the number of lines covering the zero elements is not equal to the number of rows, return to step 6.
  9. 9
    Image titled Matrix9_628
    Select a matching by choosing a set of zeros so that each row or column has only one selected.
  10. 10
    Notice that D has not been used
    Apply the matching to the original matrix, disregarding dummy rows.
    This shows who should do which activity, and adding the costs will give the total minimum cost.

Tips

  • If you wish to find a maximum matching rather than a minimum, multiply each number by -1 in step 1, then follow the steps as written.

Things You'll Need

  • Paper
  • Pen/pencil

Article Info

Featured Article

Categories: Featured Articles | Mathematics