Task: Given a weighted complete bipartite graph G = (XÈY, X×Y), where edge xy has weight w(xy), find a matching M from X to Y with maximum weight.
In an application, X could be a set of workers, Y could be a set of jobs, and w(xy) could be the profit made by assigning worker x to job y.
By adding virtual jobs or workers with 0 profitability, we may assume that X and Y have the same size, n, and can be written as X = {x_{1}, x_{2}, ..., x_{n}} and Y = {y_{1}, y_{2}, ..., y_{n}}.
Mathematically, the problem can be stated: given an n×n matrix W, find a permutation p of {1, 2, 3, ..., n} for which

Such a matching from X to Y is called an optimal assignment.
Definition: A feasible vertex labeling in G is a realvalued function l on XÈY such that for all x Î X and y Î Y,

It is always possible to find a feasible vertex labeling. One way to do this is to set all l(y) = 0 for y Î Y and for each x Î X, take the maximum value in the corresponding row, i.e.

If l is a feasible labeling, we denote by G_{l} the subgraph of G which contains those edges where l(x)+l(y) = w(xy), together with the endpoints of these edges. This graph G_{l} is called the equality subgraph for l.
Theorem. If l is a feasible vertex labeling for G, and M is a complete matching of X to Y with M Í G_{l}, then M is an optimal assignment of X to Y.
Proof: We must show that no other complete matching can have weight greater than M. Let any complete matching M¢ of X to Y be given. Then

Thus the problem of finding an optimal assignment is reduced to the problem of finding a feasible vertex labeling whose equality subgraph contains a complete matching of X to Y.
The KuhnMunkres Algorithm (also known as the Hungarian method).
Start with an arbitrary feasible vertex labeling l, determine G_{l}, and choose an arbitrary matching M in G_{l}.


Choose a vertex y in J_{Gl}(S), not in T. If y is matched in M, say with z Î X, replace S by SÈ{z} and T by TÈ{y}, and go to step 2. Otherwise, there will be an Malternating path from x to y, and we may use this path to find a larger matching M¢ in G_{l}. Replace M by M¢ and go to step 1.