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.