'Almost-stable' matchings in the hospitals / residents problem with couples: An integer programming approach

Manlove, D. and McBride, I. and Trimble, J. (2016) 'Almost-stable' matchings in the hospitals / residents problem with couples: An integer programming approach. [Data Collection]

Original publication URL: http://arxiv.org/abs/1602.01956
Enlighten Publications URI: http://eprints.gla.ac.uk/id/eprint/121248

Collection description

The Hospitals / Residents problem with Couples (hrc) models the allocation of intending junior doctors to hospitals where couples are allowed to submit joint preference lists over pairs of (typically geographically close) hospitals. It is known that a stable matching need not exist, so we consider min bp hrc, the problem of finding a matching that admits the minimum number of blocking pairs (i.e., is “as stable as possible”). We show that this problem is NP-hard and difficult to approximate even if each couple finds only one hospital pair acceptable. However if we further assume that the preference list of each single resident and hospital is of length at most 2, we give a polynomial-time algorithm for this case. We then show how to adapt an earlier Integer Programming (IP) model for hrc to yield an IP formulation for min bp hrc. Finally, we discuss an empirical evaluation of the IP model applied to randomly-generated instances of min bp hrc. Our main finding is that the number of blocking pairs admitted by a solution is very small, i.e., usually at most 1, and never more than 2, for the (28,000) instances considered.

College / School: College of Science and Engineering > School of Computing Science
Date Deposited: 18 Apr 2016 08:45
Retention date: 18 April 2026
Funder's Name: Engineering & Physical Sciences Research Council (EPSRC), Engineering & Physical Sciences Research Council (EPSRC)
URI: http://researchdata.gla.ac.uk/id/eprint/303

Available Files

Data

Read me

Repository Staff Only: Update this record

Manlove, D. and McBride, I. and Trimble, J. (2016); 'Almost-stable' matchings in the hospitals / residents problem with couples: An integer programming approach

University of Glasgow

10.5525/gla.researchdata.303

Retrieved: 2017-11-18

Downloads

Downloads per month over past year