A C implementation of the Hungarian Methodby brian gerkey email@example.com
UPDATE: Try Myriam Abramson's Java implementation, with test data.
UPDATE: Check out Cyrill Stachniss's implementation, which does not suffer from the endless loop problem mentioned in the NOTE below.
This package contains a C implementation (plus, as of version 0.3, Python bindings written by Dylan Shell), of Harold Kuhn's well-known Hungarian Method for solving Optimal Assignment Problems. The running time for this algorithm on an mXn problem is O(m*n^2), which correlates well with my own experience with this implementation.
The API is straightforward; see test.c for an example.
NOTE: hungarian_solve() seems to hang on certain extreme (degenerate?) inputs, especially when the rating matrix is non-square. I don't know what's causing this problem.