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:

  1. Let and start with an arbitrary matching 
  2. If saturates every vertex in X, stop. Otherwise, let u be an -unsaturated vertex in X.  Set .
  3. If then , since . Stop, since the Hall's theorem there is no matching that saturates every vertex in X. Otherwise, let .
  4. If y is -saturated, let . Replace S by and T by and go to the Step 3. (Observe that is maintained after this replacement.)
  5. Otherwise, let P be an M-augmenting path. Replace by and , go to Step 2.