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 [4]

in the suggested readings.

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

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

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

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 [3] 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, [1] 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}}.

Suggested Readings

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 [2] 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.