CSCI 3160 Design and Analysis of Algorithms Tutorial 9 Chengyu Lin
CSCI 3160 Design and Analysis of Algorithms Tutorial 9 Chengyu Lin
Outline ·Stable Matching ·Secretary Problem
Outline • Stable Matching • Secretary Problem
Stable Matching 免 免免 Figures borrowed from Lecture Notes of CSCI2110
Stable Matching Figures borrowed from Lecture Notes of CSCI2110
Perfect Matching in Bipartite Graph Given a bipartite graph G(V,W,E)with IVI Wl, 。. Matching:a collection of vertex-disjoint edges Perfect matching:every vertex gets matched Men Women
Perfect Matching in Bipartite Graph • Given a bipartite graph G(V, W, E) with |V| = |W|, • Matching: a collection of vertex-disjoint edges • Perfect matching: every vertex gets matched Men Women
Preference Each man has a preference list of all women Each woman has a preference list of all men Assume there is no tie Men Women 1:CBEAD A:35214 2:ABECD B:52143 3:DCBAE C:43512 4:ACDBE D:12345 5:ABDEC E:23415
Preference Men Women 1: CBEAD A : 35214 2 : ABECD B : 52143 3 : DCBAE C : 43512 4 : ACDBE D : 12345 5 : ABDEC E : 23415 • Each man has a preference list of all women • Each woman has a preference list of all men • Assume there is no tie