Mar 28, 2017
Day 87 - Stable Marriage
I love the seriously dated names involved in this problem. Anyway, the stable marriage problem assigns pairs of things based on the preferences of those things. With people, for instance, Abe has a list of preferences of who he’d like to marry, so does Abi, so does everyone else. A marriage is considered stable if there is not another person that either person wants more that is not already in a stable marriage. Essentially, any more preferred people are already in stable marriages. Ignoring the terminology for now (it was though up in 1962, a different time), it turns out to be a very useful strategy for things like matching clients to servers in distributed networks, or finding kidney matches.