The stable marriage problem is a well-known combinatorial problem with an equally well-known solution: the Gale-Shapley algorithm. This algorithm and its variants are used to solve similar problems, such as assigning teachers to classes and matching residents to hospitals. The National Resident Matching Program (NRMP) is used in the US for this purpose.

However, resident couples seeking positions in geographically similar places often face difficulties. Issues occur when one member of the couple has a much higher ranking than the other. In these cases, the existence of a stable matching is nondeterministic polynomial-time (NP) complete. However, empirical studies in practical, real-life situations have demonstrated that, in practice, stable matchings do exist. The problem then is to use a suitable heuristic to find one.

The Scottish hospital system recently decided to accommodate couples; thus, it required a new computer program to make the placements. This paper reports on the algorithm used by the Scottish Foundation Allocation Scheme (SFAS), comparing it with an algorithm used by NRMP and a simpler algorithm. The authors ran many experiments using different variants of the heuristics, simulated preference lists, and various large and small sample sizes.

The authors found that as the ratio of couples to single applicants increases, the difficulty of finding a stable matching also increases. Even so, the likelihood of finding a suitable matching is very high for realistic values of the ratio and the total number of applicants. Some variants of the heuristics perform better than others, depending on the ratios and total numbers. The paper’s many charts present these results.

This clearly written paper would be interesting to two groups of researchers: those interested in heuristic combinatorics, and those who have to deal with similar problems in their practice, such as personnel placement agencies and human resource (HR) departments.