[part 1 is not necessary to follow this] When I first looked up the Hungarian algorithm on Wikipedia, I was immediately drawn away from what seemed like a tortured graphical explanation and went straight to the rather simpler matrix represented solution. I was tempted to lookup the explanation for the algorithm in the original paper but I resisted; I wanted to work out the reason for the steps in the algorithm myself; and – joy upon joy – the explanation is beautifully symmetrical.
Let be the set of matrices with non-negative entries. comprises of all the problem sets definable for tasks and people. Let be the cost of the minimal-cost assignment for matrix . Let’s see if there is a transformation of that doesn’t affect the solution.
Proposition Let and be the transpose. Then .
Proof: If make up the indices of a minimal assignment, then make up those in . Thus, .
Proposition Let and let for and be the operation where adds to row . Then, .
Proof In a minimal assignment, exactly one cell is selected from every row. Therefore, adding to row means every possible assignment (minimal or not) increases in total cost by .
Being symmetrical to the problem, these operations and can be composed. Not only that but is its own inverse and is the inverse for . A group is formed. For our purposes, composition is going to allow us to perform steps in sequence while inverses ensure that our steps are reversible – taking us back to the original problem.
Steps 1 and 2
Step 1 is the composition of the transformations for , , and .
Step 2 is the composition of the above transformations applied to the transpose of the matrix at the end of step 1.
Now that we have at least one zero in each row, the task now is to assign as many tasks as possible such that the total cost is zero. How can we do this without resorting to brute-force? The explanations I found were confusing to say the least and I decided to see if I can work it out myself. Here’s what I came up with.
- Consider that the first people have been given the best assignment such that meaning the th person is assigned task (obviously ) and meaning no task was assigned to the th person.
- We encounter two possible cases when trying to assign a task for the th person.
- CASE 1: There exists with such that where . In which case, set .
- CASE 2: No such exists. The question is, can we re-adjust the assignments for the first people such that can be given an assignment? The solution can be written in terms of the simple linear algorithm that determines if a vertex in a graph is reachable from another. See if you can spot how it works in the following example.
Explaining the example: Column 4 is not used which can be used by row 1 (i.e. acting as the starting vertex), 2) the next row can take the column currently taken by row 1 (i.e. an edge connects rows if takes column and has a in the same column), which recursively repeated leads to 3) row 4 that can finally take the column of row 3.
In general, the assignment for the th row is determined by finding a path from a row with a zero in a free column to the th row by traversing edges connecting two rows if the second can take the column currently taken by the first. If no such path exists, then the $(k+1)th row has no assignment.
If every person was given a task the algorithm stops. Otherwise, we create a new zero in the matrix by first minimally covering the existing zeros (see the Wikipedia link), computing the minimum from the uncovered cells, and then applying the row operations to uncovered rows , , and the column operation, , to covered columns .
There you have it. A problem solved purely by reducing it with symmetrical transforms (the cleverness going into determining which symmetries to apply!). With the Hungarian algorithm, I decided to make it my contribution to the newly developing
Statistics.Matrix module – right now I use
hmatrix for my matrix needs which plugs-in to the C LAPACK/BLAS libraries – that’s part of the excellent
statistics package. The pull request is here.