The Hospitals / Residents Problem with Couples: Complexity and Integer Programming Models
The Hospitals / Residents Problem with Couples: Complexity and Integer Programming Models
复制标题
DOI：
10.1007/978-3-319-07959-2_2
复制
发表时间：
2013-08
期刊：
影响因子：
--
通讯作者：
P. Biró;D. Manlove;Iain McBride
中科院分区：
文献类型：
--
作者：
P. Biró;D. Manlove;Iain McBride
夫妻之间的医院/住院医生问题（hrc）是典型的医院/住院医生问题（hr）的概括，在实际应用中很重要，因为它模拟了夫妻共同提交偏好清单而不是对（通常是地理上接近的）医院的情况。本文给出了在hrc的高度限制情况下是否存在稳定匹配问题的一个新的np -完备性结果，以及在hrc的同等限制情况下寻找具有最小块对数目的匹配的一个不可逼近界。此外，我们给出了第一个整数规划模型的完整描述，用于在hrc实例中寻找最大基数稳定匹配，我们描述了将该模型应用于随机生成的hrc实例时的经验结果。
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 ofhrc, and also an inapproximability bound for finding a matching with the minimum number of blocking pairs in equally restricted instances ofhrc. Further, we present a full description of the first Integer Programming model for finding a maximum cardinality stable matching in an instance ofhrcand we describe empirical results when this model applied to randomly generated instances ofhrc.