Assignment problem: Hungarian method 2

Assignment Problem: Hungarian method from Tobias Huber, Philipp Motsch & Marc Sarvas

Theory:

The hungarian method is a special form of the linear optimazation. We assume that the initial matrix is a n x n matrix. The main goal is to reduce the matrix column by column and line by line until you get a unique allocation.

The hungarian method can be displayed in the following steps:

1. Determine the column minima and write every minima of the columns into the row vj.

2. Subtract the column minima from the elements of the corresponding columns.

3. Determine the row minima and write every minima of the rows into the column ui.

4. Subtract the row minima from the elements of the corresponding rows. We obtain a matrix with at least one "0" in each row and column.

5. Determine the maximal number of indepentent "0" in the matrix. First, find a row or a column which has a minimal number of "0". Mark a "0" and wipe all of the remaining "0"`s of the same row and column.

6. If the maxinmal number of independent "0" does not equal the number of row or column, determine the minimal number of lines which cover all the "0"`s. This number is equal to the maximal number of independent "0"`s.

7. Step 7 is composed of the sub-steps a) - h):

a) Mark each row, which has no marked "0" by using a cross X.

b) Mark each cloumn which obtains a discarded "0" in a marked row.

c) Mark each row, which contains a marked "0" in a marked column.

d) Repeat step b) and c) as long as there are no rows and columns to be marked.

e) Cross out each row which has not been marked, as well as each column which is marked.

f) Determine the minimum among the elements which have not been crossed out.

g) Subtract this minimum from all of the elements which have not been crossed out and add it to the elements which have been crossed out doubly.

h) Because each row and each column contains at least one "0", one can determine the maximal number of the independent "0" again.

--> If the maximal number of independent "0"`s is not equal to the number of row and column, repeat step a) - h)

Example:

There are 6 jobs for 6 candidates. The goal is to allocate the jobs to the candidates in a way where the costs are minimal.