REAL

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

[img]
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.

Item Type: Book Section
Uncontrolled Keywords: marriage; STABLE MATCHINGS
Subjects: H Social Sciences / társadalomtudományok > H Social Sciences (General) / társadalomtudomány általában
SWORD Depositor: MTMT SWORD
Depositing User: MTMT SWORD
Date Deposited: 01 Mar 2016 13:35
Last Modified: 01 Mar 2016 13:35
URI: http://real.mtak.hu/id/eprint/33945

Actions (login required)

Edit Item Edit Item