The Hospitals / Residents problem with couples: Complexity and integer programming models

Biro, P. and Manlove, D. and McBride, I. (2014) The Hospitals / Residents problem with couples: Complexity and integer programming models. [Data Collection]

Collection description

The Hospitals / Residents problem with Couples (hrc) is a generalisation of the classical Hospitals / Residents problem (hr) that is important in practical applications because it models the case where couples submit joint preference lists over pairs of (typically geographically close) hospitals. In this paper we give a new NP-completeness result for the problem of deciding whether a stable matching exists, in highly restricted instances of hrc, and also an inapproximability bound for finding a matching with the minimum number of blocking pairs in equally restricted instances of hrc. Further, we present a full description of the first Integer Programming model for finding a maximum cardinality stable matching in an instance of hrc and we describe empirical results when this model applied to randomly generated instances of hrc.

College / School: College of Science and Engineering > School of Computing Science
Date Deposited: 20 Jan 2016 13:43
Enlighten Publications URL: http://eprints.gla.ac.uk/97774
Retention date: 29 June 2024
Funder's Name: Engineering & Physical Sciences Research Council (EPSRC)
URI: http://researchdata.gla.ac.uk/id/eprint/254

Available Files

Data

Read me

Repository Staff Only: Update this record

Biro, P. and Manlove, D. and McBride, I. (2014); The Hospitals / Residents problem with couples: Complexity and integer programming models

University of Glasgow

10.5525/gla.researchdata.254

Retrieved: 2017-09-21

Downloads

Downloads per month over past year