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.
Start with bipartite graphs
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 iN1 jN2 all (i,j)
2. undirected, convert to directed by requiring the arcs to go from N1 to N2
It is equivalent to an Assignment Problem Min 
Share with your friends: | 
