9.4. Personnel Assignment Problem.
The Problem: In
a certain company, n workers are available
for n jobs
, each worker being qualified for one or more
of these jobs. Can all the men be assigned, one man per job, to jobs for which
they are qualified?
The mathematical model:
We construct a bipartite graph G
with bipartition , where
,
and is joined to
if and only if
worker
is qualified
for job
.
The problem becomes one to determining whether or not G has a perfect matching.
We will use the
Hall's theorem: either G has such a matching or there is a subset S
of X such that .
The idea is the
following: We start with an arbitrary matching . If
saturates every
vertex in X, then it is a matching of the required type.
If not, we
choose an -unsaturated vertex u in X and
systematically search for an
-augmenting path with origin u.
If we find such
a path P, then is a larger matching than
, and hence
saturates more vertices in X.
We then repeat the procedure with instead of
.
If such a path
does not exists, the set Z of all vertices which are connected to u
by -alternating path was found. Then
satisfies
.
Let M be
a matching in G, and let u be an M-unsaturated vertex in X.
A tree is called an M-alternating
tree rooted at u if
-
-
for every vertex v of H,
the unique
-path in H is an alternating path.

Figure 9.1. A Matching M in G, and an M-alternating path
The search of an M-saturating path with origin u involves growing an M-alternating tree rooted at u. The procedure was first suggested by Edmonds (1965).
Initially, H consists of just the single vertex u. It is then grow in such a way that, at any stage
- either all vertices of H except u are M-saturated vertex different from u,
- or H contains an M-unsaturated vertex different from u.
The Hungarian Method:
- Let
and start with an arbitrary matching
- If
saturates every vertex in X, stop. Otherwise, let u be an
-unsaturated vertex in X. Set
.
-
If
then
, since
. Stop, since the Hall's theorem there is no matching that saturates every vertex in X. Otherwise, let
.
-
If y is
-saturated, let
. Replace S by
and T by
and go to the Step 3. (Observe that
is maintained after this replacement.)
-
Otherwise, let P be an M-augmenting
path. Replace
by
and
, go to Step 2.