10/09/2026
Join us next Friday, October 16th, at 2:00pm in EMS E495 for Dr. Christine Cheng's colloquium!
Title:
Bridging the Gap Between Stable Marriage and Stable Roommates: A Parameterized Algorithm for Optimal Stable Matchings
Abstract:
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.