The Hospitals/Residents Program

Rob Irving, University of Glasgow

 

General

This is a program designed to solve arbitrary instances of the hospitals / residents problem [1, 2]. It incorporates the extended version of the Gale-Shapley algorithm first published in [1], and described in detail in [2].

For a given instance of the problem, the program will find both the resident-optimal and the hospital-optimal stable matching.

The preference lists need not be complete - in other words, participants may class certain others as unacceptable. Nor need they be consistent - X may appear on Y's preference list even although Y does not appear on that of X (but in such a case X and Y cannot, of course, be paired in a stable matching).

The participants may be represented by arbitrary identifiers of up to 20 characters in length.

 

Input / output

The program is entirely text-based, reading from standard input and writing to standard output.

The required input is as follows:

 

The output consists of:

Assumptions

 

Source code

The src folder contains the source code, written in Ada 95. It consists of the following:

It is portable, and may be compiled with any Ada 95 compiler.

 

Executable

The bin folder contains executable versions for Windows and for Unix (PC x86 and Sparc Solaris)

together with sample input files.

 

DISCLAIMER: this program is not supported, and although it has been subjected to extensive testing, the authors cannot take responsibility for any loss etc. resulting from errors or unexpected behaviour.

Copies of the program may be made freely for private study or educational use, provided that the program headers acknowledging the authors are retained.

 

References

1. D.Gale & L.S.Shapley, College admissions and the stability of marriage, American Mathematical Monthly, 69 (1962), 9 - 15.

2. D.Gusfield & R.W.Irving, The Stable Marriage Problem: Structure and Algorithms, MIT Press, 1989.