The Optimal Assignment Problem

Task: Given a weighted complete bipartite graph G = (XY, 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 XY 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.