2016/02/05 by David F. Manlove, Manlove, David F., Iain McBride +3
Computer Science · Economics, Econometrics and Finance · #Bayesian Modeling and Causal Inference #Data Structures and Algorithms (cs.DS) #FOS: Computer and information sciences #Game Theory and Voting Systems
paper · pdf · doi:10.48550/arxiv.1602.01956
openalex publication_date 2016/02/05 · openalex created_date 2022/10/05 · openalex updated_date 2026/07/28
The Hospitals / Residents problem with Couples (HRC) models the allocation of\nintending junior doctors to hospitals where couples are allowed to submit joint\npreference lists over pairs of (typically geographically close) hospitals. It\nis known that a stable matching need not exist, so we consider MIN BP HRC, the\nproblem of finding a matching that admits the minimum number of blocking pairs\n(i.e., is "as stable as possible"). We show that this problem is NP-hard and\ndifficult to approximate even in the highly restricted case that each couple\nfinds only one hospital pair acceptable. However if we further assume that the\npreference list of each single resident and hospital is of length at most 2, we\ngive a polynomial-time algorithm for this case. We then present the first\nInteger Programming (IP) and Constraint Programming (CP) models for MIN BP HRC.\nFinally, we discuss an empirical evaluation of these models applied to\nrandomly-generated instances of MIN BP HRC. We find that on average, the CP\nmodel is about 1.15 times faster than the IP model, and when presolving is\napplied to the CP model, it is on average 8.14 times faster. We further observe\nthat the number of blocking pairs admitted by a solution is very small, i.e.,\nusually at most 1, and never more than 2, for the (28,000) instances\nconsidered.\n