# Assignments and Matchings Match workers to jobs, etc

 Page 1/2 Date 26.04.2018 Size 231.73 Kb. #46865
1   2
##### Assignments and Matchings

Match workers to jobs, etc.

Two types of problems

1. Cardinality

Find matching with maximum number of arcs

2. Weighted problem

Weight on each arc

Find match with greatest total weight

What is the relationship between the cardinality problem and the weighted cardinality problem?

We only consider perfect matches: Ones in which in a match each node is incident to exactly one arc.

N1 N2 all arcs (i, j) i  N1 j  N2

Read the applications in section 12.2

Bipartite Cardinality Match

G= (N1  N2, A)

If the graph is undirected make it directed with all arcs going from N1 to N2

1 1

.

.

.

.

.

.
2 2

n1 n2

1 1

S
.

.

.

.

.

.
2 2 t

n1 n2

Solve a maximum flow problem from s to t.
Can show a 1-1 correspondence with the original problem.

Can solve in O(m(n)1/2)

Bipartite weighted matching problem
G= (N1  N2, A) |N1| = |N2|
Find a perfect match with minimum weight
If:

1. directed iN1 jN2 all (i,j)

2. undirected, convert to directed by requiring the arcs to go from N1 to N2