# Munkres' (Hungarian) Algorithm

## Description

The Hungarian algorithm solves instances of the assignment problem. The assignment problem belongs to the general class of matching problems. The idea benind it is very easy to grasp. It is about matching things that belong in two separate sets in a way that maximizes (or minimizes) the sum of some quantities. These quantities are typically benefits or costs associated with each matching and expressed numerically. Each object in one set can be matched with only one object from the other set. The desirable outcome is the one that maximizes the sum of benefits or, conversely, minimizes the sum of the costs.

If you are confused, let me try to clarify with an example. Consider two spatial scenes, each having two buildings. We have a [2]x[2] table describing how different the buildings of one scene are to those of the other (table of differences). The scores could be from 0 to 1, with 0 meaning that there is no difference (i.e., the objects are identical) and 1 meaning that the objects exhibit maximum dissimilarity. Alternatively, we could have the table of similarities describing how similar each building of one scene is to that of the other, where the meanings of 1 and 0 are now reversed: 1 means identical and 0 totally different. In this example we assume that the similarity is calculated as the inverse of difference (Sim=1-Diff).

 A B A B A' 0.3 0.9 A' 0.7 0.1 B' 0.5 0.2 B' 0.5 0.8 Differences Similarities

The question is how to perform the mapping so as to minimize the sum of differences or, to maximize the sum of similarities. The two statements are equivalent and both correspond to the assignment problem's formulation. Apparently, there are two possible scenarios:
(a) take the pairs (A, A'), (B, B') (the red combination) and
(b) take the pairs (A, B'), (B, A') (the yellow combination).
In our example it is apparent that the winning assignment is the red one.

The formal name of what we have done is minimum-cost (or maximum- weight) maximum cardinality matching on a bipartite graph. Our example was trivial, but for larger array dimensions things quickly get out of control (try doing the same with a [4]x[4] matrix). The reason is that with brute-force approaches one has to consider n! (n factorial) combinations where n is the dimension of the matrix. The factorial complexity is prohibiting even for computers, since a fast computer would need about 10,000 years for a [20]x[20] matrix. That's a long time to wait.

The Hungarian algorithm reduces the complexity to O(N³). However, it is a very cumbersome algorithm to implement. I provide two versions of it, one that can be used as a method call from within your program (clean version) and another one that demonstrates the inner workings of the algorithm by outputting at the console information about what is happening during each step of operation (educational version). The educational version also contains a wealth of comments inside the code. It is a great tool for those willing to understand the internal operation of the algorithm but it does not explain WHY the algorithm does the things it does...this is a matter of theory (network flows, augmenting paths etc); it only explains WHAT it does.

For a more thorough explanation of the problem you may check this page that contains a nice example and the pseudocode on which I was based to write this program. LEDA and this page provide an explanation in terms of graph theory, and information about other efficient matching algorithms.

## Technical Info

1. Release Date: May 12, 2005.
2. Type of Application: Console.
3. Version: 0.11
4. Language: JAVA.
5. Coded in: Eclipse 3.1 Milestone 6 Release.
6. Minimum Requirements: JDK 1.5.0_01 or better.
7. Tested on: Windows XP SP2.

## Algorithm Licence Agreement

You may freely redistribute this source code, as long as the comments in the headers of the source files—with the exception of sections in brackets— remain unaltered.

This code is provided on an "AS-IS" basis, without any warranties, and you use it entirely at your own risk.