3. Stable Marriage

Competitive ProgrammingWeek 03

This lecture is based on the “Stable Matching” problem (Europe - Southeastern ICPC Regionals 2007), and you can find a link to it here.

You can also find the problem on Codechef.

This video discusses the solution, the implementation is demonstrated in the next part.

Notice that the ICPC version of the problem asks for a “male optimal” stable matching, and it turns out that the algorithm we have described also has this extra property. Can you prove it?

You can revisit this algorithm in this excellent Numberphile video.

The landmark paper describing the algorithm that we discussed here.

An entire course about matchings under preferences:

The Wikipedia page for stable matching: