Example.
b) Show by an interchange argument
k i
ak ai
mk mi
mi ak versus mi ai
mk ai mk ak
Solving bipartite weighted watching problems
In general, solve bipartite weighted watching problems or assignment problem using
Successive shortest path algorithm
Augment 1 unit of flow each iteration  n1=|N1|
Find Path through iN1
Hungarian algorithm
A Primal – Dual Implementation
Can use cost scaling
No longer delayed with nonsaturating pushes since uij = 1 
n men
w women
Each man ranks all the women
Each woman ranks all the men
A man – woman pair is unstable if they are not matched together but the man prefers the woman to his current match & woman prefers the man to her current match.
We want a stable perfect matching – no unstable matches
Can find for any set of rankings
Application medical student & hospital match
Begin with 1 student per hospital
How do we solve this problem?
Two n x n matrices
Student’s hospital preferences
Hospital’s student preferences
Assume each student can go to each school
Use an iterative greedy algorithm
Each school offers to its most desired student
Each student accepts most preferred school, and rejects the others
LIST has schools without students
Each one has current – student (who to offer a position next)
Initially LIST = N1, current – student 1st in list
Select school from LIST, i, offer to its current – student
If matched, student keeps current school or i whichever they prefer more
- if student switches from k to i
k goes onto list, current – student updated
- else i stays on list, update current student
Continue until LIST is empty
Called “propose – and – reject” algorithm
Algorithm Comments
Is stable
If school i wants student 1, student 1 will be at i unless
i full – with students that are more preferred
student 1 is picked up by a different school that was more preferred (possibly after student 1 took an offer from one or more schools)
student never switches to a less preferable school
0 (n2)
student either
accepts 1st
switches
can do this max n-1 times
(n-1) switches n students
0(n2)
Many stable matchings – possibly
Can show that the school is as well off as with any stable match
Each school gets best possible stable partner
Thus, school optimal
Student never rejects a stable school partner (can prove this)
Can show student gets worst possible stable match (can prove this)
How would we modify this if each school accepts more than 1 student?
Nonbipartite cardinality matching on an undirected network.
Definition
Matching M of G = (N,A)
Subset of arcs such that no two arcs in M are incident to the same node
Arcs in M matched
Arcs not in M unmatched
Nodes incident to arcs in M matched
Other nodes unmatched
If (i, j) is in the matching we say i is matched to j & j is matched to i
In the subgraph defined by the match, nodes have degree 0 or 1
n/2 - maximum number of arcs in the match
Alternating path & cycle
P = i1 – i2 …. ik is an alternating path with respect to M if every consecutive pair of arcs has 1 matched arc & 1 unmatched arc
Example
Ex: 1 – 3 – 5 – 6 – 4 – 2
Even alternating path even # arcs
Odd alternating path odd # arcs
Alternating cycle 3 – 5 – 6 – 4 – 3
Augmenting path
Odd alternating path with first & last nodes unlabeled
Ex: 1 – 3 – 5 – 6 – 4 – 2
Can Mto M + 1 by reversing matched & unmatched arcs on path
Symmetric difference of two sets
s1, s2 two sets
s1 s2 = (s1s2) - (s1s2) Like exclusive or
s1 = { 1, 2, 4, 7} s2 = {1, 3, 4, 6, 8}
s1 s2 = {2, 3, 6, 7, 8}
Property 12.6 If M is a matching and P is an augmenting path with respect to M, then M P is a matching of cardinality M+ 1. Moreover, in the matching M P, all the matched nodes in M remain matched and two additional nodes, namely the first and last nodes of P are matched.
Property 12.7 If M and M* are two matchings their symmetric difference defines the subgraph G* (N, M M*) with the property that every component is one of the six types shown in Figure 12.7.
Theorem 12.8 If a node p is unmatched in a matching M and this matching contains no augmenting path that starts at node p, then node p is unmatched in some maximum matching.
Plausible algorithm
Start with a feasible M (maybe null)
For an unmatched p N, try to identify an augmenting path
If we find one, P, replace M w/ M P
Else drop p & all arcs incident to it from the graph
By theorem 12.8, the augmenting path theorem, this algorithm will find an optimal solution.
Is it easy to determine if an augmenting path exists?
How to do the search for an augmenting path
Grow a tree rooted at p
Call the tree an alternating tree
Nodes in the alternating tree are labeled
Other nodes are unlabeled
Labeled nodes are
Even if there are an even number of arcs in the unique path from root (p) to node i
Odd if there are an odd number of arcs in the unique path from root (p) to node i
After labeling an even node, scan the adjacency list and give an odd label to unlabeled nodes. If one of the odd labeled nodes, j, is unmatched you found an augmented path, otherwise add j to LIST.
After labeling an odd node, look at matched arc (j, k) - if k is unlabeled give k an even label and add it to LIST.
When an unmatched node has an odd or even label do we have an augmenting path?
Why?
Example:
Unique label property
Unfortunately, the method just described only works if graphs possess the unique label property (bipartite ones do).
Unique label property. A graph is said to possess a unique label property with respect to a given matching M and a root node p if the search procedure assigns a unique label to every labeled node (i.e., even or odd) irrespective of the order in which it examines labeled nodes.
But nonbipartite graphs may not satisfy this property
Example.
Contracting a blossom
In a blossom each node could be odd or even.
If odd -can only label other nodes in the blossom (only label using arcs in M from the current node).
If even – can label all nodes in adjacency list.
Want to label all as even- do this by contracting the nodes of the blossom into a single node
Contraction
Replace blossom, B, i1-i2-…ik-il with a pseudonode b. (always even)
Introduce b, Adj. list A(b)= A(i1)A(i2) ….A(ik)
Update A(j) for all j A(b) A(j)= A(j) {b}
To uncontract later form a circular doubly linked list of nodes in b.
Call new net Gc=(Nc,Ac)
Contracted net
Correctness
1.Show when there is an augmenting path in the contracted network we can find one in the original.
2. By contracting blossoms we don’t add or omit augmenting paths.
Complexity O(n3)
Bipartite O(nm)
Matchings and Paths
Shortest path in a directed network from s to t.
Can transform if there are no negative cycles to an Assignment Problem
Solve two assignment problems
The first determines if there is a negative cycle in the graph.
The second application solves the shortest path problem.
Shortest path in an undirected network.
A bit more complicated, you can read it on your own.
Share with your friends: | 
