The Optimal Assignment Problem

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 = {x1, x2, ..., xn} and Y = {y1, y2, ..., yn}.

Mathematically, the problem can be stated: given an n×n matrix W, find a permutation p of {1, 2, 3, ..., n} for which

 n å i = 1 w(xiyp(i))
is a maximum.

Such a matching from X to Y is called an optimal assignment.

Definition: A feasible vertex labeling in G is a real-valued function l on XÈY such that for all x Î X and y Î Y,

 l(x) + l(y) ³ w(xy).
Such labelings may be conveniently written beside the matrix of weights.

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.

 l(x) = max y Î Y w(xy)
 for x Î X
 l(y) = 0
 for y Î Y

If l is a feasible labeling, we denote by Gl the subgraph of G which contains those edges where l(x)+l(y) = w(xy), together with the endpoints of these edges. This graph Gl 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 Í Gl, 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

 w(M¢)
 =
 å xy Î M¢ w(xy)
 £
 å xy Î M¢ (l(x)+l(y))     (feasibility of l)
 =
 å xy Î M (l(x)+l(y))     (all the l(x) and l(y) are summed in either matching)
 =
 å xy Î M w(xy)     since M Í Gl
 =
 w(M).

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 Kuhn-Munkres Algorithm (also known as the Hungarian method).

Start with an arbitrary feasible vertex labeling l, determine Gl, and choose an arbitrary matching M in Gl.

1. If M is complete for G, then M is optimal. Stop. Otherwise, there is some unmatched x Î X. Set S = {x} and T = Æ.
2. If JGl(S) ¹ T, go to step 3. Otherwise, JGl(S) = T. Find
 al = min x Î S, y Î Tc {l(x)+l(y)-w(xy)}
where Tc denotes the complement of T in Y, and construct a new labeling l¢ by
l¢(v) = ì
ï
ï
í
ï
ï
î
 l(v) - al
 for v Î S
 l(v) + al
 for v Î T
 l(v)
 otherwise
Note that al > 0 and JGl¢(S) ¹ T. Replace l by l¢ and Gl by Gl¢.
3. Choose a vertex y in JGl(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 M-alternating path from x to y, and we may use this path to find a larger matching M¢ in Gl. Replace M by M¢ and go to step 1.

File translated from TEX by TTH, version 1.57.