Colloquium: Dr. Christine Cheng
October 16 @ 2:00 pm - 3:00 pm
Bridging the Gap Between Stable Marriage and Stable Roommates: A Parameterized Algorithm for Optimal Stable Matchings
An instance of the Stable Roommates (SR) problem consists of 2n agents, each with a preference
list that linearly orders the other agents. The goal is to find a perfect matching that is stable – one
with no pair of agents who mutually prefer each other to their assigned partners. In this talk, I
consider the problem of finding an optimal stable matching. An efficient algorithm exists for Stable Marriage (SM) instances, the bipartite version, but the problem is NP-hard for SR instances. I will sketch a solution showing how an optimal stable matching for an SR instance can be obtained by “covering” it with SM instances.
In particular, the closer the SR instance is to an SM instance, the more efficient is the solution.
list that linearly orders the other agents. The goal is to find a perfect matching that is stable – one
with no pair of agents who mutually prefer each other to their assigned partners. In this talk, I
consider the problem of finding an optimal stable matching. An efficient algorithm exists for Stable Marriage (SM) instances, the bipartite version, but the problem is NP-hard for SR instances. I will sketch a solution showing how an optimal stable matching for an SR instance can be obtained by “covering” it with SM instances.
In particular, the closer the SR instance is to an SM instance, the more efficient is the solution.
Check here for more information!
