The hospitals / residents problem with couples

Biró, Péter and Manlove, DF. and McBride, I. (2014) The hospitals / residents problem with couples. In: Experimental algorithms. Lecture Notes in Computer Science (8504). Springer, Cham (Németország), pp. 10-21. ISBN 978-3-319-07958-5

Preview

Text BMcBM14lncs_last.pdf Download (674kB) | Preview

Abstract

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 geographi- cally 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 find- ing 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 sta- ble matching in an instance of hrc and we describe empirical results when this model applied to randomly generated instances of hrc.

Actions (login required)

Edit Item