##### 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
N_{1} N_{2} all arcs (i, j) i N_{1} j N_{2 }
Read the applications in section 12.2
**Bipartite Cardinality Match **
G= (N_{1} N_{2}, A)
If the graph is undirected make it directed with all arcs going from N_{1} to N_{2}
1 1
**.**
**.**
**.**
**.**
**.**
**.**
2 2
n_{1} n_{2}
1 1
S
**.**
**.**
**.**
**.**
**.**
**.**
2 2 t
n_{1} n_{2}
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= (N_{1} N_{2}, A) |N_{1}| = |N_{2}|
Find a perfect match with minimum weight
If:
1. directed iN_{1} jN_{2} all (i,j)
2. undirected, convert to directed by requiring the arcs to go from N_{1} to N_{2}
## It is equivalent to an Assignment Problem ## Min
**Share with your friends:** |