A MAXIMUM STABLE MATCHING FOR THE ROOMMATES PROBLEM

Abstract

The stable roommates problem is that of matching n people into n/2 disjoint pairs so that no two persons, who are not paired together, both prefer each other to their respective mates under the matching. Such a matching is called "a complete stable matching". It is known that a complete stable matching may not exist. Irving proposed an O(n2) algorithm that would find one complete stable matching if there is one, or would report that none exists. Since there may not exist any complete stable matching, it is natural to consider the problem of finding a maximum stable matching, i.e., a maximum number of disjoint pairs of persons such that these pairs are stable among themselves. In this paper, we present an O(n2) algorithm, which is a modified version of Irving's algorithm, that finds a maximum stable matching.