The Assignment Problem

Author: Fred J. Rispoli, Department of Mathematics, Dowling College.
Prerequisites: The prerequisites for this chapter are matrices, permutations,
and basic concepts of graphs. See Sections 3.8, 5.3, 9.1, and 9.2 of Discrete
Mathematics and Its Applications.
Introduction
Consider the following problem: Given n workers (i = 1, 2,…,n) and n jobs
(j = 1, 2,…,n), and the cost cij to train the ith worker for the jth job, find
an assignment of one worker to each job which minimizes the total training
cost. This problem is an example of an assignment problem, which we will
define shortly. The assignment problem is particularly interesting because many
seemingly different problems may be solved as assignment problems. Moreover,
it is an important example of a combinatorial optimization problem; that is, a
problem that seeks the best possible arrangement of objects among a specified
set of many possible arrangements. Typically, the best possible arrangement
means an arrangement with the smallest total cost possible.
Let us begin by looking at some examples.
Example 1 Job Assignment Suppose three workers must be assigned to
299
300 Applications of Discrete Mathematics
three jobs. The following matrix shows the cost of training each worker for each
job.
Job Number
?
?
123
1 579
Worker Number 2 14 10 12
3 15 13 16
?
?.
One possible assignment is to assign worker 1 to job 2, worker 2 to job 1,
and worker 3 to job 3. This assignment has a total cost of 7 + 14 + 16 = 37. Is
this an assignment with minimal total cost? We will discover the answer later
in this chapter.
Example 2 The Marriage Problem A pioneering colony of 10 bachelors
is joined by 10 prospective brides. After a short period of courting, it is decided
to have an immediate ceremony. Each bride is given a list of 10 names on which
she is to rank her preferences from 1 to 10; that is, she assigns 1 to her first
choice, 2 to her second choice, and so on. Let cij be the rank bride i gives to
bachelor j, and let M = {(1, j1),(2, j2),…,(10, j10)} be a set of 10 marriages
where (i, ji) pairs bride i with bachelor ji. Then we assume that n
i=1 ciji
constitutes a valid measure of the anticipated ?happiness? of the colony under
the set of marriages M, in the sense that the smaller the sum, the happier the
colony. What set of 10 marriages maximizes the happiness of the colony?
Example 3 The Shortest Path Problem Cargo must be delivered by
train from New York to Los Angeles. The train routes available are shown in
Figure 1, along with the time (in hours) required for each route. Notice that
the time depends on the direction since some routes are express routes while
others are not. What path from New York to Los Angeles gives the smallest
total delivery time?
Figure 1. Train routes and times.
Chapter 17 The Assignment Problem 301
These problems are all examples of problems which may be solved as assignment
problems. In this chapter we will derive an efficient algorithm for
solving assignment problems, and then discuss several problems which may be
solved using this algorithm. The assignment problem will then be described in
terms of graphs.
Solving Assignment Problems
Recall that a permutation of a set N = {1, 2,…,n} is a function s : N ? N
which is one-to-one and onto. For example, the function from {1, 2, 3, 4, 5}
to itself where s(1) = 5, s(2) = 4, s(3) = 2, s(4) = 1, and s(5) = 3, is a
permutation which we denote 54213.
Definition 1 Given any n ? n matrix C = [cij ], the assignment problem
specified by C is the problem of finding a permutation s of {1, 2,…,n} that
minimizes
z = n
i=1
cis(i).
One method for solving assignment problems is to generate all n! permutations
of {1, 2,…,n} (a method for doing this is given in Section 5.6 of Discrete
Mathematics and Its Applications), compute
z = n
i=1
cis(i)
for each permutation s, and then find a permutation on which the minimum of
z is attained.
Example 4 In the job assignment problem described in Example 1 of the
Introduction, there are 3! = 6 permutations:
s1 = 123 cost: 31
s4 = 312 cost: 36
s2 = 132 cost: 30
s5 = 231 cost: 34
s3 = 213 cost: 37
s6 = 321 cost: 34.
Thus, s2 solves the problem and indicates that the best assignment is to assign
worker 1 to job 1, worker 2 to job 3, and worker 3 to job 2.
The above method is helpful only for n quite small, since one must check
all n! possibilities. In practice assignment problems often have n = 30. If each
302 Applications of Discrete Mathematics
permutation can be generated in just 10-9 seconds, an assignment problem
with n = 30 would require at least 8 ? 1015 years of computer time to solve by
generating all 30! permutations. Therefore a better method is needed.
Before developing a better algorithm, we need to set up a model for the
assignment problem. Let C = [cij ] be any n ? n matrix in which cij is the cost
of assigning worker i to job j. Let X = [xij ] be the n ? n matrix where
xij =
1 if row i is assigned to column j (that is,
worker i is assigned to job j)
0 otherwise
The assignment problem can then be expressed in terms of a function z as:
minimize z(X) = n
i=1
n
j=1
cijxij ,
subject to the constraints
n
j=1
xij = 1, for i = 1, 2,…,n (1)
n
i=1
xij = 1, for j = 1, 2,…,n (2)
Notice that condition (1) guarantees that each row subscript i is assigned to
exactly one column subscript. Condition (2) guarantees that each column subscript
j is assigned to exactly one row subscript. Hence any matrix X satisfying
conditions (1) and (2) is called a solution and corresponds to a permutation s
of N obtained by setting s(i) = j if and only if xij = 1. Furthermore, if X is a
solution corresponding to s, then
n
j=1
cijxij = cis(i).
Summing over i from 1 to n, we obtain
n
i=1
cis(i) = n
i=1
n
j=1
cijxij .
Thus, any solution X on which z(X) is minimum is called an optimal solution.
For instance, in Example 1 it was noted that the permutation s2 given
by 132 gives the best possible assignment of workers to jobs for that assignment
problem. The permutation s2 corresponds to the matrix
X* =
?
?
100
001
010
?
? .
Chapter 17 The Assignment Problem 303
Since
C =
?
?
579
14 10 12
15 13 16
?
? ,
we have
z(X*) = 
3
i=1

3
j=1
cijx*
ij = 5 + 12 + 13 = 30.
This model allows for the derivation of an efficient algorithm known as
the Hungarian method. The idea behind the Hungarian method is to try to
transform a given assignment problem specified by C into another one specified
by a matrix C
= [
cij ], such that
cij = 0, for all pairs i, j, where both problems
have the same set of optimal solutions. We then find a solution X* for which
z
(X*) = n
i=1
n
j=1

cijx*
ij = 0.
Since
cij = 0 (and hence z
(X) = 0 for all X), X* must be an optimal
solution to the problem specified by C
, and hence must also be an optimal
solution to the one specified by C. Theorem 1 describes how we can transform
a matrix into another one which has the same set of optimal solutions.
Theorem 1 A solution X is an optimal solution for
z(X) = n
i=1
n
j=1
cijxij
if and only if it is an optimal solution for
z
(X) = n
i=1
n
j=1

cijxij
where
cij = cij -ui -vj for any choice of (u1,…,un) and (v1,…,vn) where ui
and vj are real numbers for all i and j.
Proof: We will show that the functions z(X) and z
(X) differ only by the
constant n
i=1 ui + n
j=1 vj .
304 Applications of Discrete Mathematics
z
(x) = n
i=1
n
j=1

cijxij
= n
i=1
n
j=1
(cij – ui – vj )xij
= n
i=1
n
j=1
cijxij -n
i=1
n
j=1
uixij -n
i=1
n
j=1
vjxij
= n
i=1
n
j=1
cijxij -n
i=1
n
j=1
uixij -n
j=1
n
i=1
vjxij
= z(x) -n
i=1
ui
n
j=1
xij -n
j=1
vj
n
i=1
xij
= z(x) -n
i=1
ui -n
j=1
vj .
The last equation follows from conditions (1) and (2). This shows that
z(X) – z
(X) = n
i=1
ui +n
j=1
vj .
Thus, a solution X minimizes z(X) if and only if it minimizes z
(X).
To describe an optimal solution in terms of entries of a matrix the following
notion of independent entries is needed. A set of entries of any matrix A is said
to be independent if no two of them are in the same row or column.
Example 5 Apply Theorem 1 to the matrix given in Example 1 to obtain
a new matrix with all nonnegative entries, which contains an independent set
of three zeros and has the same set of optimal solutions as the original matrix.
Solution: Let
C =
?
?
579
14 10 12
15 13 16
?
? .
Subtract from each entry in each row the smallest entry in that row; that is,
let u1 = 5, u2 = 10, u3 = 13, and v1 = v2 = v3 = 0. This gives the matrix
?
?
024
402
203
?
? .
Chapter 17 The Assignment Problem 305
The new matrix has an independent set of two zeros, but we need three. Next,
subtract from each entry in each column the smallest entry in that column, that
is, let u1 = u2 = u3 = 0, v1 = v2 = 0, and v3 = 2. This gives
C
=
?
?
0* 2 2
4 00*
2 0* 1
?
? .
The starred entries in C
form an independent set of three zeros. By Theorem 1
applied twice, C
and C have the same set of optimal solutions.
We are interested in obtaining a matrix with nonnegative entries with an
independent set of three zeros because it is easy to obtain an optimal solution
from such a matrix, as Example 6 illustrates.
Example 6 Solve the assignment problem specified by
C =
?
?
579
14 10 12
15 13 16
?
? ,
by obtaining an optimal solution to the problem specified by
C
=
?
?
0* 2 2
4 00*
2 0* 1
?
? .
Solution: Define the solution
X* =
?
?
100
001
010
?
? .
Then X* solves the assignment problem specified by C
since z
(X*) = 0 and
z
(X) = 0 for any other solution X. By Example 5, X* is also an optimal
solution to the assignment problem specified by C. Note that X* corresponds
to the permutation 132.
The method used to obtain an optimal solution to the assignment problem
specified by C
in Example 6 is generalized in Theorem 2.
306 Applications of Discrete Mathematics
Theorem 2 If C = [cij ] satisfies cij = 0 for all i and j (1 = i = n, 1 =
j = n), and {c1j1 , c2j2 ,…,cnjn } is an independent set of n zeros in C, then
X* = [x*
ij ] where x*
1j1 = 1, x*
2j2 = 1,…,x*
njn = 1, and x*
ij = 0 for any other i
and j, is an optimal solution to the assignment problem specified by C.
Proof: We must show that for any solution X, z(X) = z(X*). To see this,
observe that
z(X*) = n
i=1
n
j=1
cijx*
ij
= n
i=1
cijix*
iji
= 0.
The second step follows from the definition of X*, and the last step follows
since ciji = 0 for all i. Since z(X) = 0 for all solutions X, z(X) = z(X*), so X*
is an optimal solution.
The objective of the Hungarian method is to use Theorem 1 to transform a
matrix C into another matrix C
, having the same set of optimal solutions as C,
such that C
contains an independent set of n zeros. Then, using Theorem 2,
an optimal solution to both problems can be obtained.
Example 7 Use Theorem 1 to transform
C =
?
?
0 16
2 -7 3
-534
?
?
into a matrix with nonnegative entries containing an independent set of 3 zeros.
Then use Theorem 2 to obtain an optimal solution to the assignment problem
specified by C.
Solution: Let u1 = 0, u2 = -7, u3 = -5, and v1 = v2 = v3 = 0. Then apply
Theorem 1 to obtain the matrix
?
?
01 6
9 0 10
08 9
?
? ,
which has the same set of optimal solutions as C. This matrix does not have
an independent set of 3 zeros. Letting u1 = u2 = u3 = v1 = v2 = 0 and v3 = 6
gives
C
=
?
?
0 10*
9 0* 4
0* 8 3
?
? ,
Chapter 17 The Assignment Problem 307
which also has the same set of optimal solutions as C. By Theorem 2,
X* =
?
?
001
010
100
?
?
is an optimal solution to the problem C
, hence to the problem C. Note that X*
corresponds to the permutation 321.
The matrix C
in the solution of Example 7 is called a reduced matrix for C,
which we shall now define.
Definition 2 Given any n ? n matrix C = [cij ], let
ui = minimum {ci1, ci2,…,cin}, for i = 1, 2, . . . , n,
vj = minimum {c1j – u1, c2j – u2,…,cnj – un}, for j = 1, 2, . . . , n.
The n ? n matrix C
= [
cij ] given by
cij = cij – ui – vj for all pairs i and j is
called the reduced matrix for C.
In words, a reduced matrix is obtained by first subtracting from each row
the smallest entry in each row and then subtracting from each column the smallest
entry in each column. By Theorem 1, the assignment problems specified
by a matrix C and by its reduced matrix C
both have the same set of optimal
solutions. Observe that all entries in the reduced matrix are nonnegative.
However, the reduced matrix may not contain an independent set of n zeros.
Example 8 Determine the reduced matrix for
C =
?
?
257
421
265
?
? .
Solution: The values of u1, u2, u3, v1, v2, and v3, as defined in the definition
of the reduced matrix are u1 = 2, u2 = 1, u3 = 2, and v1 = 0, v2 = 1, and
v3 = 0. Therefore, the reduced matrix is
C
=
?
?
025
300
033
?
? .
308 Applications of Discrete Mathematics
The matrix C
in the solution of Example 8 does not contain an independent
set of three zeros. To obtain a new matrix having the same optimal solutions
as C
, but containing more zeros, draw a set of lines through the rows and
columns of C
using as few lines as possible so that there is at least one line
through every zero. This gives
C
=
?
?
025
300
033
?
? .
Observe that the minimum number of lines needed to cover all zeros is
equal to the maximum number of independent zeros. Theorem 3, which we
will need in order to show that the Hungarian method terminates after a finite
number of steps, shows that this fact is true in general.
Theorem 3 The maximum number of independent zeros in a matrix is equal
to the minimum number of lines needed to cover all zeros in the matrix.
The proof is beyond the scope of the book. For a proof of Theorem 3, see 
Example 9 Use Theorem 1 to transform the reduced matrix
C
=
?
?
025
300
033
?
?
from Example 8 into a matrix with nonnegative entries containing an independent
set of three zeros.
Solution: First, subtract from every entry in C
the smallest entry not covered
by any line (which is 2). This is the transformation with u1 = u2 = u3 = 2 and
v1 = v2 = v3 = 0, and gives the matrix
?
?
-20 3
1 -2 -2
-21 1
?
? .
Next, add 2 to every entry in every row and column covered by one line,
and add 2 twice to any entry covered by two lines (note that the (2, 1)entry
has 2 added to it twice, since it was covered twice). This is the transformation
u1 = u3 = v2 = v3 = 0 and u2 = v1 = 2, and gives the matrix
?
?
0 0* 3
5 00*
0* 1 1
?
?
which contains an independent set of three zeros.
Chapter 17 The Assignment Problem 309
The Hungarian Method
We will now display the algorithm called the Hungarian method. We shall
assume that the costs cij are integers. To begin the algorithm, given an n ? n
matrix C, first obtain the reduced matrix C
for C; that is, subtract from each
entry of each row the smallest entry in that row. Then do the same for columns.
Next perform the following two steps:
(i) Find a maximal independent set of zeros. If this set has n elements,
an optimal solution is available. Otherwise go to step (ii).
(ii) Find a set of lines that cover all zeros using the smallest possible
number of lines. Let k be the smallest entry not covered. Subtract
k from each entry not covered by any line, and add k to each entry
covered twice. Repeat step (i).
Algorithm 1 gives the pseudocode description of the Hungarian method.
Applying step (ii) of the algorithm produces a new matrix with the same
set of optimal solutions as the original matrix, since step (ii) is equivalent to
first subtracting k from every entry in the matrix, and then adding k to every
entry covered by a line. Subtracting k from every entry is the transformation
ui = k, for all i, and vj = 0, for all j. By Theorem 1, this does not change
the set of optimal solutions. Adding k to every entry covered by a line is the
transformation
ui =
 -k if there is a line through row i
0 otherwise
vj =
 -k if there is a line through column j
0 otherwise.
Again by Theorem 1, this does not change the set of optimal solutions.
We now show that the algorithm must terminate after a finite number of
steps. (We leave it as Exercise 13 to show that, after performing the initial
step, all entries in the reduced matrix are nonnegative.) We will show that
the sum of all entries in the matrix decreases by at least 1 whenever step (ii) is
performed. Clearly, if the sum of all entries is zero, then all entries in the matrix
are zero and an independent set of n zeros exists. Thus, if the algorithm did
not terminate, the sums of all matrix entries would give an infinite decreasing
sequence of positive integers, which is impossible.
Step (ii) is performed only when no independent set of n zeros exists. Thus,
if q is the minimum number of lines needed to cover all zeros, then Theorem 3
implies that q of entries, since there are n2 entries in the matrix. Adding k to each covered
entry adds qkn to the sum of entries, since there are q lines and n entries on
each line. Therefore the net change in the sum of entries is -kn2 + qkn. But
-kn2 + qkn = kn(-n + q) < 0, since q the sum of all entries must decrease by at least 1.
310 Applications of Discrete Mathematics
ALGORITHM 1. Hungarian Method
procedure Hungarian (C: n?n matrix of integers) for i :=
1 to n
begin
ui := smallest integer in row i of C
for j := 1 to n

cij := cij – ui
end
for j := 1 to n
begin
vj := smallest integer in column j of Cfor i := 1 to n

cij :=
cij – vj
end
{C
is now the reduced matrix}
S := an independent set of zeros of maximal size in Cq := |S|
while q begin
cover (C
)
k := smallest entry in C
not covered by a line
for i := 1 to n
for j := 1 to n
begin
if
cij is not covered then
cij :=
cij – k if
cij
is covered twice then
cij :=
cij + k
end
S := an independent set of zeros of maximal size in C
q :=
|S|
end for i := 1 to n
for j := 1 to n
if
cij ? S then x*
ij := 1 else x*
ij := 0
{X* = [x*
ij ] is an optimal solution}
Exercise 17 shows that the number of iterations is O(n2). To compare the
Hungarian method to the exhaustive search method mentioned above, suppose
that each iteration can be performed in one second. Then an assignment problem
with n = 30 can be solved in at most 302 = 900 seconds, or 15 minutes of
Chapter 17 The Assignment Problem 311
computer time.
The following example illustrates how the Hungarian method works.
Example 10 A foreman has five workers and five jobs to complete. The
time in hours each worker needs to complete each job is shown in the following
table.
Job 1 Job 2 Job 3 Job 4 Job 5
Worker 1 3487 8
Worker 2 2532 6
Worker 3 7918 3
Worker 4 5346 6
Worker 5 8975 8
How should the foreman make an assignment of one worker to each job so that
the total time is minimized?
Solution: Let
C =
?
????
34878
25326
79183
53466
89758
?
???? .
The reduced matrix is
?
????
01543
03102
68070
20131
34201
?
???? .
The minimum number of lines needed to cover all zeros of this matrix is four.
For example, lines through row 3 and through columns 1, 2 and 4 will cover all
zeros. Since we need an independent set of 5 zeros, step (ii) must be performed.
This gives the matrix
?
????
0* 1442
0 3 00* 1
7 90* 8 0
2 0* 030
3 4 1 00*
?
???? .
The starred entries indicate one possible independent set of five zeros. Thus an
312 Applications of Discrete Mathematics
optimal solution is
X* =
?
????
10000
00010
00100
01000
00001
?
???? ,
which corresponds to the permutation 14325. An optimal job assignment is to
assign Worker 1 to Job 1, Worker 2 to Job 4, Worker 3 to Job 3, Worker 4 to
Job 2, and Worker 5 to Job 5.
Example 11 Find a path which minimizes total delivery time from New
York to Los Angeles in the shortest path problem given in Figure 1.
Solution: We solve the assignment problem specified by the following matrix.
Exercise 16 shows that any optimal solution of this assignment problem will
find a path which minimizes total delivery time. We assign a time of 100 hours
to any route joining a pair of cities for which there is no train route. The choice
of 100 prohibits such a route from occurring as part of an optimal solution.
This is because the path
New York ? Dallas ? Los Angeles
is a path with total time 74 hours. Hence, any path which minimizes total
delivery time can have a total time of at most 74 hours, so any route requiring
more than 74 hours can not be part of an optimal solution.
Bos Chi Dal Den S F L A
N Y 6 25 34 100 100 100
Bos 0 18 100 100 100 100
Chi 100 0 20 15 100 50
Dal 100 18 0 100 100 40
Den 100 15 100 0 20 100
S F 100 100 100 26 0 6
By applying the Hungarian method, the optimal solution
X* =
?
??????
100000
010000
000100
001000
000010
000001
?
??????
is obtained (details are left as Exercise 5). This matrix shows that the shortest
path is
Chapter 17 The Assignment Problem 313
Figure 2. Job assignments.
N Y ? Bos ? Chi ? Den ? S F ? L A.
(Note that the path does not pass through Dallas.)
The Hungarian method was discovered in 1955 by Harold Kuhn* of the
Mathematics and Economics Departments of Princeton University (see  in
the suggested readings for the original paper). The algorithm is called the
?Hungarian? method in honor of Denes K?onig**, who, in 1931, discovered Theorem
3. There are other efficient algorithms for solving the assignment problem.
For example,  in the suggested readings describes an algorithm based on the
degrees of vertices of certain spanning trees of Kn,n, the complete bipartite
graph.
Perfect Matching Problems
Suppose four workers must be assigned to four jobs. The jobs that each worker
can perform are indicated by an edge of the graph given in Figure 2. Is it
possible to assign workers to jobs so that each worker is assigned one job and
each job is assigned to one worker?
This problem may also be stated in terms of graphs. We need the following
definition.
* Harold Kuhn (1925? ) is an American mathematician who obtained his Ph.D.
from Princeton University. Kuhn has made many fundamental contributions to the
field of linear programming and is most famous for the Kuhn-Tucker conditions which
characterize the set of optimal solutions of a linear program.
** Denes K?onig (1884?1944) was a Hungarian mathematician. He is known as one
of the pioneers of graph theory and is most famous for his work in matching theory.
314 Applications of Discrete Mathematics
Definition 3 Let G = (V,E) be any bipartite graph with V = V1 ? V2. A
subset of edges M contained in E is called a perfect matching if every vertex
in V is contained in exactly one edge of M.
For example, the bipartite graph given in Figure 3a contains the perfect
matching given in Figure 3b.
Figure 3. A bipartite graph and a perfect matching.
The problem stated in the beginning of this section may now be stated as
follows. Does there exist a perfect matching in the graph given in Figure 2? The
problem of determining if a given bipartite graph contains a perfect matching
was solved by Georg Frobenius* who proved the well known ?Marriage Theorem?.
To state this theorem we will use the following notation: for any subset W
contained in V1 let R(W) denote the set of vertices in V2 adjacent to a vertex
in W.
Theorem 4 Frobenius Marriage Theorem A bipartite graph G = (V,E)
with V = V1 ?V2 has a perfect matching if and only if |V1| = |V2| and for every
subset W contained in V1, |R(W)|=|W|.
The proof of Theorem 4 may be obtained by applying Theorem 3. The
details are left for Exercises 18 and 19.
Example 12 Determine if the graph given in Figure 2 contains a perfect
matching.
Solution: Let W = {Worker 1, Worker 2, Worker 3}. Then R(W) = {Job 1,
Job 3}. Since |R(W)| = 2 and |W| = 3, Theorem 4 implies that the graph
given in Figure 2 does not contain a perfect matching.
* Georg Frobenius (1848?1917) was a German mathematician who attended schools
in G?ottingen and Berlin. He was a professor of mathematics at both the University
of Berlin and the Eidgenossische Polytechnikum in Zurich. Frobenius is best known
for his contributions to algebra, particularly in group theory.
Chapter 17 The Assignment Problem 315
The weight of any perfect matching M is the sum of the weights of the
edges in M. Many matching problems involve searching a weighted bipartite
graph for a perfect matching which has the smallest possible weight.
Example 13 Suppose three workers must be assigned to three jobs. The
graph given in Figure 4 indicates the cost of training each worker for each job.
How should the workers be assigned to jobs so that each worker is assigned one
job, each job is assigned one worker, and the total training cost is minimized?
Figure 4. Training costs.
Solution: We solve the problem by listing the set of all perfect matches along
with their weights:
M1 = {{1, 1}, {2, 2}, {3, 3}} weight: 31
M2 = {{1, 1}, {2, 3}, {3, 2}} weight: 30
M3 = {{1, 2}, {2, 1}, {3, 3}} weight: 37
M4 = {{1, 3}, {2, 1}, {3, 2}} weight: 36
M5 = {{1, 2}, {2, 3}, {3, 1}} weight: 34
M6 = {{1, 3}, {2, 2}, {3, 1}} weight: 34
This shows that M2 is the perfect matching with the smallest possible
weight. Thus Worker 1 should be assigned to Job 1, Worker 2 should be assigned
to Job 3, and Worker 3 should be assigned to Job 2.
The reader should compare the perfect matches listed in the solution to
Example 13 and the permutations s1,…,s6 listed in Example 4. Note that
the permutation s1 given by s1(1) = 1, s1(2) = 2, and s1(3) = 3, corresponds
to the perfect matching M1, which matches 1 to 1, 2 to 2, and 3 to 3. The
permutation s2 given by s2(1) = 1, s2(2) = 3, and s2(3) = 2, corresponds to
316 Applications of Discrete Mathematics
the perfect matching M2 which matches 1 to 1, 2 to 3, and 3 to 2. Similarly
the permutations s3, s4, s5, and s6 correspond to the perfect matches M3,
M4, M5, and M6 respectively. Therefore, solving Example 13 is equivalent to
solving the assignment problem specified by
C =
?
?
579
14 10 12
15 13 16
?
?
solved earlier. This is not a coincidence. Given any weighted complete bipartite
graph Kn,n, any perfect matching M corresponds to a permutation s of
{1, 2,…,n} defined by s(i) = j if and only if edge {i, j} ? M. Moreover, if
the weight of edge {i, j} is cij , then
weight of M = n
i=1
cis(i).
Thus, finding a perfect matching of minimum weight in a complete bipartite
graph is equivalent to solving the assignment problem specified by C = [cij ].
In fact, finding a perfect matching with the smallest possible weight is simply
a search for the best possible assignment of the vertices in V1 to those in V2.
Example 14 Find a perfect matching with the smallest possible weight for
the graph given in Figure 5.
Figure 5. A weighted graph.
Solution: The problem is solved by solving the assignment problem specified
by
?
?
382
911
549
?
? .
Applying the Hungarian method gives the reduced matrix
?
?
0* 6 0
7 00*
0 0* 5
?
?
Chapter 17 The Assignment Problem 317
which contains an independent set of 3 zeros. An optimal solution is
?
?
100
001
010
?
?
which corresponds to the perfect matching M = {{1, 1}, {2, 3}, {3, 2}}.
1. M. Balinski, ?Signature Methods for the Assignment Problem?, Operations
Research, Vol. 33, 1985, pp. 527?536.
2. D. Gale and L. Shapley, ?College Admissions and the Stability of Marriage?,
American Mathematical Monthly 69, 1962, pp. 9?15.
3. H. Kuhn, ?The Hungarian Method for the Assignment Problem? Naval
Res. Logist. Quart., Vol. 2, 1955, pp. 83?97.
4. M. Hall, Combinatorial Theory, Second Edition, John Wiley & Sons, Hoboken,
N.J., 1998.
Exercises
In Exercises 1?4, solve the assignment problem specified by the given matrix.
1.
?
??
5839
2619
3948
4729
?
?? .
2.
?
??
6258
6716
6347
5435
?
?? .
318 Applications of Discrete Mathematics
3.
?
??????
759786
124131
998893
475634
537435
322121
?
??????
.
4.
?
??????
-6 3 1 0 46
5 -38 4 53
-5 4 9 8 93
3 75 -809
7 2 6 5 76
-302 -134
?
??????
.
5. Solve the assignment problem specified by the matrix in the solution to
Example 11.
6. The coach of a certain swim team needs to assign swimmers to a 200-yard
medley relay team . Most of his swimmers are quite fast in more than
one stroke, so it is not clear which swimmer should be assigned to each of
the four strokes. The four fastest swimmers and the best times they have
achieved in each of the strokes, for 50 yards, are
Stroke Ken Rob Mark David
Backstroke 39.3 33.6 34.0 35.6
Breaststroke 34.2 41.8 38.7 33.7
Butterfly 29.5 30.6 33.1 31.8
Freestyle 28.7 27.6 30.3 29.3
How should the coach assign the four swimmers to the four different strokes
to minimize the sum of the corresponding best times?
7. Find a set of marriages which maximizes the ?happiness? of the following
colony of 6 prospective brides and 6 bachelors, where the rating of the
bachelors by the brides is given in the following table.
John Bill Joe Al Bud Hal
Jane 3 4 1 2 5 6
Mary 2 5 3 6 4 1
Carol 2 3 1 5 3 6
Jessica 1 2 5 6 3 4
Dawn 5 4 2 1 6 3
Lisa 4 3 6 2 1 5
Chapter 17 The Assignment Problem 319
8. The following figure indicates available train routes along with the time
required to travel the route. Find a route from Boston to San Francisco
which minimizes total time required.
9. Determine which of the following bipartite graphs contain a perfect matching.
List the edges in a perfect matching for those graphs that contain one,
and show that Frobenius? Marriage Theorem does not hold for those graphs
that do not contain a perfect matching.
a)
b)
c)
10. Find a perfect matching with the smallest possible weight in the following
weighted graph. The weights of the edges are given in the following table.
320 Applications of Discrete Mathematics
V2
V1
1234
1 3683
2 2567
3 6259
4 4352
11. a) Construct a 5?5 matrix C such that the assignment problem specified
by C has more than one optimal solution.
b) Construct a 5?5 matrix C such that the assignment problem specified
by C has a unique optimal solution.
12. Show that any permutation of {1, 2, 3, 4} solves the assignment problem
specified by
?
??
1234
5678
9 10 11 12
13 14 15 16
?
?? .
13. Explain why the entries in the reduced matrix are nonnegative, even if the
original costs are negative.
14. Given any n ? n matrix C, describe how the Hungarian Method may be
used to solve an assignment problem in which we seek a permutation s of
{1, 2,…,n} such that n
i=1 cis(i) is maximum.
15. Use Exercise 14 to find a permutation which maximizes n
i=1 cis(i), where
C is the matrix given in Exercise 3.
16. Show that any optimal solution to the assignment problem specified by
the matrix given in Example 11 finds a path from New York to Los Angeles
which minimizes total delivery time. Hint: Suppose s* is an optimal
solution and P is a path shorter than n
i=1 cis*(i).
17. Show that the Hungarian Method uses O(n2) iterations to find an optimal
solution of an assignment problem.
Chapter 17 The Assignment Problem 321
A vertex cover Q of the edges of a graph G is a set of vertices such that each
edge of G contains at least one vertex in Q.
18. Show that in a bipartite graph G = (V,E) the maximum number of edges
in a matching is equal to the minimum number of vertices in a vertex cover.
Hint: Use Theorem 3.
19. Use Exercise 18 to prove Theorem 4.
Suppose that in a community of n bachelors together with n prospective brides
each person ranks those of the opposite sex in accordance with his or her
preferences for a marriage partner. A set of n marriages is called unstable if
among the n marriages there are a man and a woman who are not married to
each other, but prefer each other to the person they are married to; otherwise
the set of marriages is called stable. (For a complete discussion of stable
marriages see  in the suggested readings.)
20. If the first number of the following table gives the preferences of women by
the men and the second number gives the preferences of men by the women,
find a stable set of 4 marriages.
Susan Colleen Nancy Dawn
David 1,1 2,3 3,2 4,1
Richard 2,3 1,4 3,1 4,4
Paul 1,4 4,1 2,3 3,3
Kevin 3,2 1,2 4,4 2,2
21. Prove that in any community of n men and n women there always exists a
stable set of n marriages. Hint: Construct an iterative procedure for finding
a stable set of n marriages.
Computer Projects
1. Write a program that inputs a 5 ? 5 matrix C and solves the assignment
problem specified by C by generating all the permutations of {1, 2, 3, 4, 5}.
2. Write a program that inputs a 5?5 matrix C and finds an independent set
of zeros of maximum size in C.