The Hungarian algorithm, also known as the Kuhn-Munkres algorithm, is well-known to be the most efficient algorithm for solving the assignment problem. In fact, it does what is considered by many to an exponential time algorithm (more specifically, factorial time), in O(n3).
The Wikipedia page describes the general form of the problem quite well.
There are a number of agents and a number of tasks. Any agent can be assigned to perform any task, incurring some cost that may vary depending on the agent-task assignment. It is required to perform all tasks by assigning exactly one agent to each task in such a way that the total cost of the assignment is minimized.
However, the implementation of this algorithm is far from trivial. In fact, for all my Googling, not a single implementation in C# turned up (though there was at least one in each of C, C++, Java, and Python). Given this opportunity, I took on the task of porting this code given on this page in the Ada language, to C# 3.0. With almost 300 lines of code, and a bit of debugging with the sample problem,
The algorithm is contained within a single static class that exposes an extension method that operates on a matrix (2D array), for ease of use. Although I believe that as an almost line-for-line port of the Ada code, there should not be any issues with my implementation, any bug reports would be appreciated.
Updated 15/10/09: Several bug fixes have been made that fix issues (most noticeably, endless looping) for non-square as well as various other sorts of matrices.
Updated 24/10/09: Fixed bug (endless looping) that affects large variety of matrices, involving ConvertPath function.